問題
大人気の新作ゲーム機 「Nanteaho SWAP 2」の抽選に見事当選したoさんは、根強い人気を誇るレースゲーム「Bit Kart」の最新作であり、
SWAP2のローンチタイトルであるゲーム「Bit Kart XORWORLD」を遊んでいる。
このレースゲームは初心者でも遊びやすいように運の要素が大きくなっており、逆転するためのアイテムが獲得できるアイテムボックス付近では大きな順位変動が起こる。
具体的には、$2^{k}$ 人のプレイヤーがいるとき、 $i$ 位( $1 \leq i \leq 2^{k}$ )のプレイヤーの順位は $(i-1) \oplus (2^{k}-1) + 1$ 位になる。
本作には、$2^{N}$ 人のプレイヤーが最後の一人になるまで生き残りをかけてレースを行う新モード「サバイバル」が収録されており、
oさんはこのモードのオンライン対戦で優勝を目指している。
このモードでは、一つのコースに $N$ 個の区間があり、各区間について、最初から数えて $i$ 番目( $1 \leq i \leq N$ )の区間には $B_i$ 個のアイテムボックスがある。
各区間を走り終えた際に順位が低かった半数のプレイヤーが脱落し、
残りの半分のプレイヤーはその順位のまま次の区間へ進むことができる。最後の区間を走り終えた際に1位だったプレイヤーが優勝となる。
さて、オンライン対戦の環境ではプレイヤー全員のスキルが高いため、アイテムボックス付近以外では全く順位変動が起こらない。
この状況でoさんが優勝するためには、何位でスタートすれば良いか求めよ。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $B_1$ $B_2$... $B_N$
1行目にプレイヤーの数を表す自然数 $N$ が与えられる。
2行目では、 $N$ 個の区間についての各区間のアイテムボックスの数 $B_i$ が与えられる。
出力
oさんが優勝するためには、何位でスタートすれば良いかを出力せよ。
出力の最後に改行すること。
制約
全ての入出力ケースについて以下を満たす。
- $ 1\leq N \leq 16$
- $ 1\leq B_i \leq 10^{18}$
入出力例
入力例1
3 1 1 1
出力例1
6
oさんの順位は、$6$ (スタート時) → $(6-1) \oplus (2^3-1) + 1 = 5 \oplus 7 + 1 =3$(区間$1$終了時)
→ $(3-1) \oplus (2^2-1) + 1 = 2 \oplus 3 + 1 = 2$(区間$2$終了時)
→ $(2-1) \oplus (2^1-1) + 1 = 1 \oplus 1 + 1 = 1$(区間$3$終了時) となり、oさんの優勝です。
入力例2
2 2 2
出力例2
1
このときoさんは区間 $1$ と 区間 $2$ のどちらも終了時に $1$ 位になっています。
入力例3
5 1 2 3 4 5
出力例3
26