题目背景

题目描述

众所周知，某位被女士秒杀的风之神温迪喜欢削山。因为削山会把树也弄没，从而导致空没法撸树和吃苹果了。于是温迪开始种苹果树。

由于神力的作用，温迪种的苹果树都是二叉树，并且每个苹果都尽量长在左边，每个苹果都有一个成熟时间。现在温迪把树上苹果的成熟时间记录下来，假设苹果是一个个先后成熟的（即成熟完一个下一个才开始成熟），在空摘苹果前，祂想考考空一棵树叶子上的苹果成熟时间和。

空数学很差，于是他找到了会编程的你，让你告诉他答案，并承诺事后会给你一半的苹果。

输入格式

本题有多组测试样例。

每个测试用例都由两行组成。

第一行一个整数 $n$，代表这棵树上有 $n$ 个苹果。

第二行有 $n$ 个整数 $a_i$，分别为这棵树上苹果的成熟时间。

当 $n = 0$ 时输入结束。

输出格式

对于每个测试样例均输出一个数 $s$，代表这棵树叶子上的苹果的成熟时间和。

样例

6 1 1 4 5 1 4
7 1 9 1 9 8 1 0
0

10
18

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^6，0 \le a_i \le 100$。