帕维尔有几根长度等于 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)$$$。