AT_wtf22_day2_e Adjacent Xor Game

[problemUrl]: https://atcoder.jp/contests/wtf22-day2-open/tasks/wtf22_day2_e $ N $ 個の非負整数 $ A_1,A_2,\cdots,A_N $ が与えられます． 各 $ k=1,2,\cdots,N $ について，以下の問題を解いてください． Alice と Bob が以下のようなゲームをします． - Alice が $ A_1,A_2,\cdots,A_N $ の中から $ k $ 個の数を選ぶ． 選んだ数を $ x_1,x_2,\cdots,x_k $ (順不同)とおく． - Bob が長さ $ 2k $ の非負整数列 $ y=(y_1,y_2,\cdots,y_{2k}) $ を作る． ここで，$ y $ は以下の条件を満たす必要がある． - $ 0\ \leq\ y_1\ \leq\ y_2\ \leq\ \cdots\ \leq\ y_{2k} $ - $ z_i=y_{2i-1}\ \oplus\ y_{2i} $ と定義する． このとき，$ \{z_1,z_2,\cdots,z_k\} $ は多重集合として $ \{x_1,x_2,\cdots,x_k\} $ と一致する． なお，$ \oplus $ はビット単位 $ \mathrm{XOR} $ 演算を表します． このゲームの**スコア**を $ y_{2k} $ の値とします． Bob はスコアを最小化するように行動します． その上で Alice はスコアを最大化するように行動します． このとき，スコアはいくつになるでしょうか？ ビット単位 $ \mathrm{XOR} $ 演算とは 非負整数 $ A,\ B $ のビット単位 $ \mathrm{XOR} $ 、$ A\ \oplus\ B $ は、以下のように定義されます。 - $ A\ \oplus\ B $ を二進表記した際の $ 2^k $ ($ k\ \geq\ 0 $) の位の数は、$ A,\ B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。 例えば、$ 3\ \oplus\ 5\ =\ 6 $ となります (二進表記すると: $ 011\ \oplus\ 101\ =\ 110 $)。 一般に $ k $ 個の非負整数 $ p_1,\ p_2,\ p_3,\ \dots,\ p_k $ のビット単位 $ \mathrm{XOR} $ は $ (\dots\ ((p_1\ \oplus\ p_2)\ \oplus\ p_3)\ \oplus\ \dots\ \oplus\ p_k) $ と定義され、これは $ p_1,\ p_2,\ p_3,\ \dots,\ p_k $ の順番によらないことが証明できます。

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ．

### 制約 - $ 1\ \leq\ N\ \leq\ 250000 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力される値はすべて整数． ### Sample Explanation 1 $ k=1 $ の場合を考えます． - Alice が $ x_1=1 $ を選んだ場合: Bob は $ y=(0,1) $ を作り，スコアは $ 1 $ になります． - Alice が $ x_1=2 $ を選んだ場合: Bob は $ y=(0,2) $ を作り，スコアは $ 2 $ になります． - Alice が $ x_1=3 $ を選んだ場合: Bob は $ y=(1,2) $ を作り，スコアは $ 2 $ になります． よって Alice は $ x_1=2 $ または $ x_1=3 $ を選び， スコアは $ 2 $ になります． $ k=2 $ の場合を考えます． Alice が $ (x_1,x_2)=(2,3) $ を選び，Bob が $ y=(1,2,4,6) $ を作ると，スコアは $ 6 $ になります． これは両者の最適な行動の一例であり，求める答えは $ 6 $ です． $ k=3 $ の場合を考えます． Alice が $ (x_1,x_2,x_3)=(1,2,3) $ を選び，Bob が $ y=(0,1,1,2,4,6) $ を作ると，スコアは $ 6 $ になります． これは両者の最適な行動の一例であり，求める答えは $ 6 $ です．