Triangle Construction

문제

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

For instance, suppose that you have a regular $44$-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]A\; =\; [3,\; 1,\; 4,\; 6]$. The uppermost side is labelled as side $11$.

You want to create as many non-degenerate triangles as possible while satisfying the following requirements. Each triangle consists of $33$ distinct special points (not necessarily from different sides) as its corners. Each special point can only become the corner of at most $11$ 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.

입력

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

The following line consists of $NN$ integers $A_{i}A\_i$ (1 ≤ A_i ≤ 2 \cdot 10^9).

출력

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

4
3 1 4 6

4

6
1 2 1 2 1 2

3

3
1 1 1

1