CF1906M.Triangle Construction

You are given a regular $N$-sided polygon. Label one arbitrary side as side $1$, then label the next sides in clockwise order as side $2$, $3$, $\dots$, $N$. There are $A_i$ special points on side $i$. These points are positioned such that side $i$ is divided into $A_i + 1$ segments with equal length.

For instance, suppose that you have a regular $4$-sided polygon, i.e., a square. The following illustration shows how the special points are located within each side when $A = [3, 1, 4, 6]$. The uppermost side is labelled as side $1$.

You want to create as many non-degenerate triangles as possible while satisfying the following requirements. Each triangle consists of $3$ distinct special points (not necessarily from different sides) as its corners. Each special point can only become the corner of at most $1$ triangle. All triangles must not intersect with each other.

Determine the maximum number of non-degenerate triangles that you can create.

A triangle is non-degenerate if it has a positive area.

给你一个正 $N$-边形。任选一条边标记为第 $1$ 条边，然后按顺时针方向依次将后续各边标记为第 $2$、$3$、$\dots$、$N$ 条边。第 $i$ 条边上共有 $A_i$ 个特殊点。这些点的位置使得第 $i$ 条边被等分为 $A_i + 1$ 段（即每段长度相等）。

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

你的目标是尽可能多地构造非退化三角形，并满足以下条件：每个三角形由 $3$ 个互不相同的特殊点（不一定来自不同边）作为其顶点；每个特殊点至多只能作为 $1$ 个三角形的顶点；所有三角形彼此互不相交。

请确定你能构造出的非退化三角形的最大数目。

一个三角形是非退化的，当且仅当其面积为正。

The first line consists of an integer $N$ ($3 \leq N \leq 200\,000$).

The following line consists of $N$ integers $A_i$ ($1 \leq A_i \leq 2 \cdot 10^9$).

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

接下来的一行包含 $N$ 个整数 $A_i$（$1 \leq A_i \leq 2 \cdot 10^9$）。

Output a single integer representing the maximum number of non-degenerate triangles that you can create.

输出一个整数，表示你能构造的非退化三角形的最大数量。

Explanation for the sample input/output #1

One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.

Explanation for the sample input/output #2

One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.

样例输入/输出 #1 的说明

一种能够达到最多非退化三角形数量的构造方案如下图所示。

样例输入/输出 #2 的说明

一种能够达到最多非退化三角形数量的构造方案如下图所示。