Om Nom 是游戏“割绳子”的主角。他是一个聪明的小怪物,喜欢拜访住在公园另一边的朋友。然而,黑暗的古老公园甚至会吓到像 Om Nom 这样无所畏惧的人,所以他请求你帮助他。
公园由 2n + 1 - 1 个由道路连接的正方形组成,因此公园的方案是深度为 n 的满二叉树。更正式地说,公园的入口位于广场 1。公园的出口位于广场 2n、2n + 1、...、2n + 1 - 1,这些出口直接通向 Om Nom 朋友的房子。从每个方格 i (2 ≤ i < 2n + 1) 都有一条通往方格 $$\frac{i}{2}$$ 的路。因此,从公园入口到每个出口,可以恰好沿着n条路行走。
Om Nom 喜欢在去朋友家的路上数灯。 Om Nom 害怕公园里的蜘蛛,所以他不喜欢沿着光线不足的道路行走。他想要的是,通往他任何一个朋友的路上应该有相同数量的灯。这会让他感到安全。
他要求你帮他安装额外的灯。确定需要在公园道路上额外安装多少盏灯,以便从公园入口到任何出口的路径包含相同数量的路灯。您可以向每条道路添加任意数量的路灯。
输入
第一行包含整数 n (1 ≤ n ≤ 10) — 从入口到任意出口的路径上的道路数量。
下一行包含 2n + 1 - 2 个数字 a2, a3, ... a2n + 1 - 1 — 公园每条道路上路灯的初始数量。这里 ai 是方块 i 和 $$\frac{i}{2}$$ 之间道路上的路灯数量。所有数字ai都是正整数,不超过100。
输出
打印出我们应该在公园道路上添加的最少路灯数量,以使 Om Nom 感到安全。
示例
输入 #1
2 1 2 3 4 5 6
输出 #1
5
注意
样本测试图片。绿色表示额外的路灯。