C. DongDong拼三角形 - Alldream Monthly 2019.4 - ECNU Online Judge

你可以在这里下载。

单点时限: 1.0 sec

内存限制: 512 MB

DongDong家的萨摩耶叼来了一堆木棒，第 $i$ 种木棒的长度是 $2^{i} (2, 4, 8, 16 \dots)$ ，萨摩耶想让DongDong把这些木棒尽可能多的拼成三角形。··

输入格式

第一行一个整数 $n$

接下来一行 $n$ 个整数，分别表示第 $i$ 种木棒有多少根

输出格式

一个整数表示最多可以拼成多少个三角形。

样例

Input

5
1 2 2 2 2

Output

提示

20pts:所有种类的木棒条数都是1
50pts: $n \leq 100$
100pts: $n \leq 200000$

NaN

A. DongDong变魔法 B. DongDong爱爬山 C. DongDong拼三角形 D. DongDong跳一跳