配点 : $100$ 点

問題文

「硬度フェスティバル」は毎年開催される、世界で一番硬い石を決める大会です。

今年の硬度フェスティバルには $2^N$ 個の石が参加します。 $i$ 番目の石の硬度は $A_i$ です。

大会では石をトーナメント形式でぶつけ合って、最硬の石を決めます。

硬度 $X$ の石と硬度 $Y$ の石をぶつけると以下のような結果になります。

• $X$ > $Y$ のとき： 硬度が $Y$ だった石は砕けて、 硬度が $X$ だった石の硬度は $X-Y$ になります。 このとき硬度が $X$ だった石が勝ち残ります。
• $X$ = $Y$ のとき： どちらかの石が砕けます。もう片方の石が硬度が元と変わらないまま残ります。このとき砕けなかった方の石が勝ち残ります。
• $X$ < $Y$ のとき： 硬度が $X$ だった石は砕けて、 硬度が $Y$ だった石の硬度は $Y-X$ になります。 このとき硬度が $Y$ だった石が勝ち残ります。

$2^N$ 個の石は以下のようなトーナメント形式で勝負をします。

1. ($1$ 番目の石、$2$ 番目の石)、($3$ 番目の石、$4$ 番目の石)、... の組み合わせでぶつけ合う。
2. ($(1, 2)$ の勝ち残り、$(3, 4)$ の勝ち残り)、($(5, 6)$ の勝ち残り、$(7, 8)$ の勝ち残り)、... の組み合わせでぶつけ合う。
3. 同様に、勝ち残りが $1$ つだけになるまで続ける。

最後まで勝ち残る石の、最後の時点での硬度を求めてください。

制約

• $1 \leq N \leq 18$
• $1 \leq A_i \leq 10^9$
• $A_i$ は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$

$A_2$

$:$

$A_{2^N}$

出力

最後まで勝ち残る石の、最後の時点での硬度を出力せよ。

2
1
3
10
19

7

3
1
3
2
4
6
8
100
104

2