← 返回题目列表

Codeforces · 1119/E

E. 帕维尔和三角形

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

帕维尔有几根长度等于 2 的幂的棍子。

他有 $$$a_0$$$ 长度为 $$$2^0 = 1$$$ 的棍子, $$$a_1$$$ 长度为 $$$2^1 = 2$$$ 的棍子,..., $$$a_{n-1}$$$ 长度为 $$$2^{n-1}$$$ 的棍子。

帕维尔想用这些木棍制作尽可能多的三角形。三角形的面积必须严格为正,每根棍子最多只能用于一个三角形。

禁止折断木棍,每个三角形必须由三根木棍组成。

找出三角形的最大可能数量。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 300\,000$$$) — 不同长度的木棍的数量。

第二行包含 $$$n$$$ 整数 $$$a_0$$$, $$$a_1$$$, ..., $$$a_{n-1}$$$ ($$$1 \leq a_i \leq 10^9$$$),其中 $$$a_i$$$ 是长度等于 $$$2^i$$$ 的木棍数量。

输出

打印一个整数 - Pavel 可以制作的非退化三角形的最大可能数量。

示例

输入 #1

5
1 2 2 2 2

输出 #1

3

输入 #2

3
1 1 1

输出 #2

0

输入 #3

3
3 3 3

输出 #3

3

注意

在第一个示例中,Pavel 可以制作这组三角形(列出了三角形的边长):$$$(2^0, 2^4, 2^4)$$$, $$$(2^1, 2^3, 2^3)$$$, $$$(2^1, 2^2, 2^2)$$$。

在第二个示例中,Pavel 无法制作单个三角形。

在第三个示例中,Pavel 可以创建这组三角形(列出了三角形的边长):$$$(2^0, 2^0, 2^0)$$$, $$$(2^1, 2^1, 2^1)$$$, $$$(2^2, 2^2, 2^2)$$$。