CF1119E Pavel and Triangles

Pavel 有若干根长度为 2 的幂的木棍。 他有 $a_0$ 根长度为 $2^0 = 1$ 的木棍，$a_1$ 根长度为 $2^1 = 2$ 的木棍，……，$a_{n-1}$ 根长度为 $2^{n-1}$ 的木棍。 Pavel 想用这些木棍制作尽可能多的三角形。每个三角形必须有严格大于零的面积，每根木棍最多只能用在一个三角形中。 不允许折断木棍，每个三角形必须恰好由三根木棍组成。 请你求出 Pavel 最多可以制作多少个非退化三角形。

第一行包含一个整数 $n$（$1 \leq n \leq 300\,000$），表示不同长度的木棍种类数。 第二行包含 $n$ 个整数 $a_0, a_1, \ldots, a_{n-1}$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示长度为 $2^i$ 的木棍的数量。

输出一个整数，表示 Pavel 最多可以制作的非退化三角形的数量。

在第一个样例中，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)$。 由 ChatGPT 4.1 翻译