说明

给定一个正 $N$ 边形。任选一条边标记为第 $1$ 条边，顺时针依次标记为第 $2$ 条边、第 $3$ 条边，直到第 $N$ 条边。第 $i$ 条边上有 $A_i$ 个特殊点，这些点的位置使得第 $i$ 条边被等分为 $A_i + 1$ 段。

例如，假设你有一个正四边形（即正方形）。下图展示了当 $A = [3, 1, 4, 6]$ 时，每条边上的特殊点的分布情况。最上方的边标记为第 $1$ 条边。

:::align{center} :::

你希望在满足以下要求的前提下，构造尽可能多的不退化三角形。每个三角形由 $3$ 个不同的特殊点（不一定来自不同的边）作为顶点组成。每个特殊点最多只能作为 $1$ 个三角形的顶点。所有三角形之间不能相交。

请你求出最多可以构造多少个不退化三角形。

一个三角形是“不退化”的，当且仅当它的面积大于 $0$。

输入格式

第一行包含一个整数 $N$（$3 \leq N \leq 200\,000$）。

第二行包含 $N$ 个整数 $A_i$（$1 \leq A_i \leq 2 \cdot 10^9$）。

输出格式

输出一个整数，表示最多可以构造多少个不退化三角形。

4
3 1 4 6

4

6
1 2 1 2 1 2

3

3
1 1 1

1

提示

样例输入输出 $1$ 的解释：

下图展示了一种可以达到最大三角形数量的构造方式。

:::align{center} :::

样例输入输出 $2$ 的解释：

下图展示了一种可以达到最大三角形数量的构造方式。

:::align{center} :::

由 ChatGPT 4.1 翻译