시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB120666358.879%

문제

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.

입력

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

The following line consists of $N$ integers $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.

예제 입력 1

4
3 1 4 6

예제 출력 1

4

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

예제 입력 2

6
1 2 1 2 1 2

예제 출력 2

3

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

예제 입력 3

3
1 1 1

예제 출력 3

1