310904: CF1906M. Triangle Construction

M. Triangle Constructiontime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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$).

Output

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

ExamplesInput

4
3 1 4 6

Output

4

Input

6
1 2 1 2 1 2

Output

3

Input

3
1 1 1

Output

1

Note

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.

题目大意：给定一个正N边形，每个边上有Ai个特殊点，这些点将边等分为Ai+1段。要构造尽可能多的非退化三角形，每个三角形由3个不同的特殊点组成，每个特殊点只能成为至多1个三角形的顶点，所有三角形互不交叉。求最大可能构造的非退化三角形的数量。

输入数据格式：第一行包含一个整数N（3≤N≤200,000）。接下来一行包含N个整数Ai（1≤Ai≤2×10^9）。

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

请注意，非退化三角形是指具有正面积的三角形。题目大意：给定一个正N边形，每个边上有Ai个特殊点，这些点将边等分为Ai+1段。要构造尽可能多的非退化三角形，每个三角形由3个不同的特殊点组成，每个特殊点只能成为至多1个三角形的顶点，所有三角形互不交叉。求最大可能构造的非退化三角形的数量。 输入数据格式：第一行包含一个整数N（3≤N≤200,000）。接下来一行包含N个整数Ai（1≤Ai≤2×10^9）。 输出数据格式：输出一个整数，表示能构造的最大非退化三角形的数量。 请注意，非退化三角形是指具有正面积的三角形。