Triangle Construction

Time limit2sMemory limit1024 MB

Summary

Given a regular polygon whose sides carry A_i equally spaced points, find the most non-crossing, non-degenerate triangles with disjoint corners.

Level: Medium7 of 10
Topics: Greedy, Math, Geometry
Solved: No attempts yet

Problem

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, ..., N$ . There are $A_i$ special points on side $i$ . These points are positioned so that side $i$ is divided into $A_i + 1$ segments of 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 be a 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 contains an integer $N$ ( $3 \le N \le 200\,000$ ).

The following line contains $N$ integers $A_i$ ( $1 \le A_i \le 2 \cdot 10^9$ ).

Output

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

Examples3

Example 1
Input
```
4
3 1 4 6
```
Expected output
```
4
```
Example 2
Input
```
6
1 2 1 2 1 2
```
Expected output
```
3
```
Example 3
Input
```
3
1 1 1
```
Expected output
```
1
```