← 返回题目列表

AtCoder · relay_c

C. 科德节

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

科德节 是一项年度竞赛,确定世界上最坚硬的石头。 (Kode 是日语中“硬度”的意思。)

今年, 2^N 石头参加了。硬度 i- 第石头是 A_i.

在比赛中,淘汰赛中互相扔石头。

当两块石头具有硬度时 X 和 Y 互相投掷,会发生以下情况:

  • 当 X > Y: 石头有硬度 Y 将被摧毁并消除。 石头的硬度用硬度来表示 X 将变为 X-Y.

  • 当 X = Y: 其中一颗石头将被破坏并消除。 另一块石头的硬度将保持不变。

  • 当 X < Y: 石头有硬度 X 将被摧毁并消除。 石头的硬度用硬度来表示 Y 将变为 Y-X.

的 2^N 石头将在淘汰赛中进行如下战斗:

  1. 以下配对将进行战斗:( 1-st 石头对 2-nd 石头),( 3-rd 石头与 4第石头),...

  2. 以下配对将进行比赛:(((的获胜者)1-st 与 2-nd) 与 ( 的获胜者3-rd 与 4-th)), ( ( ( 的获胜者5-th 与 6-th) 与 ( 的获胜者7-th 与 8-th)), ...

  3. 依此类推,直到只剩下一颗石头。

确定剩余最后一块石头的最终硬度。

约束

  • 1 \leq N \leq 18
  • 1 \leq A_i \leq 10^9
  • A_i 是一个整数。

输入

输入由标准输入按以下格式给出:

N
A_1
A_2
:
A_{2^N}

输出

打印剩余最后一块石头的最终硬度。 有


示例输入 1

2
1
3
10
19

示例输出 1

7

示例输入 2

3
1
3
2
4
6
8
100
104

示例输出 2

2