题目描述

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

今年の硬度フェスティバルには $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$ つだけになるまで続ける。

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

输入格式

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

$N$ $A_1$ $A_2$ $:$ $A_{2^N}$

输出格式

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

题目大意

一共有 $2^{n}$ 个石头，现在让每个石头（如 $1$ 号和 $2$ 号石头，$3$ 号和 $4$ 号......一直到 $2^{n}-1$ 号和 $2^{n}$ 号）相互之间进行碰撞，一轮结束后，剩下的石头再次进行碰撞，直到剩下唯一的一个石头。求剩下的那个石头的硬度是多少。

关于石头碰撞时硬度的计算，有如下几点：

1. 当 $X > Y$ 时，硬度为 $X$ 的石头的硬度变为 $X-Y$，另一块石头破碎

2. 当 $X = Y$ 时，随机一块石头破碎，另一块石头硬度不变

3. 当 $X < Y$ 时，硬度为 $Y$ 的石头的硬度变为 $Y-X$，另一块石头破碎

【输入】

第一行输入 $n$

接下来 $2^{n}$ 行每行输入一个数，表示当前石头的硬度

【输出】

剩下那块石头的硬度

2
1
3
10
19

7

3
1
3
2
4
6
8
100
104

2

提示

制約

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