Pavel and Triangles
Contest: Codeforces Global Round 2
Difficulty rating: 1900
Tags: brute force, dp, fft, greedy, ternary search

Pavel has several sticks with lengths equal to powers of two.

He has $$$a_0$$$ sticks of length $$$2^0 = 1$$$, $$$a_1$$$ sticks of length $$$2^1 = 2$$$, ..., $$$a_{n-1}$$$ sticks of length $$$2^{n-1}$$$.

Pavel wants to make the maximum possible number of triangles using these sticks. The triangles should have strictly positive area, each stick can be used in at most one triangle.

It is forbidden to break sticks, and each triangle should consist of exactly three sticks.

Find the maximum possible number of triangles.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 300\,000$$$) — the number of different lengths of sticks.

The second line contains $$$n$$$ integers $$$a_0$$$, $$$a_1$$$, ..., $$$a_{n-1}$$$ ($$$1 \leq a_i \leq 10^9$$$), where $$$a_i$$$ is the number of sticks with the length equal to $$$2^i$$$.

Output format:
Print a single integer — the maximum possible number of non-degenerate triangles that Pavel can make.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, Pavel can, for example, make this set of triangles (the lengths of the sides of the triangles are listed): $$$(2^0, 2^4, 2^4)$$$, $$$(2^1, 2^3, 2^3)$$$, $$$(2^1, 2^2, 2^2)$$$.

In the second example, Pavel cannot make a single triangle.

In the third example, Pavel can, for example, create this set of triangles (the lengths of the sides of the triangles are listed): $$$(2^0, 2^0, 2^0)$$$, $$$(2^1, 2^1, 2^1)$$$, $$$(2^2, 2^2, 2^2)$$$.

Example input:
5
1 2 2 2 2

Example output:
3

Example input:
3
1 1 1

Example output:
0

Editorial:
First, possible triangles have sides $$$(2^i, 2^j, 2^j)$$$ where $$$i \le j$$$.
There are several correct greedies to finish the solution, let's discuss one of them.
The greedy is to loop through the values of $$$j$$$ in increasing order, then first try to match as many pairs $$$(j, j)$$$ to some unmatched $$$i$$$ as possible, after that create as many triples $$$(j, j, j)$$$ as possible and continue to the next $$$j$$$.
To prove correctness, let's take our solution and one of the optimal solutions. Let's find the first difference in them if we consider the triples in the same order as our solutions considers them. There can be only one type of difference: we take some triple while the optimal solution skippes it. It can't be be the other way around because we always take a triple if there is one. So there are a few cases now:
• the triple is $$$(i, j, j)$$$ where $$$i < j$$$. Let's see where the corresponding $$$i$$$, $$$j$$$ and $$$j$$$ are used in the optimal solution:   all three are used in different triples: $$$(t_1, k_1, k_1)$$$, $$$(t_2, k_2, k_2)$$$, $$$(t_3, k_3, k_3)$$$, $$$\{t_1, t_2, t_3\} = \{i, j, j\}$$$, $$$j \le k_1 \le k_2 \le k_3$$$. Remove these triples and replace them with $$$(i, j, j)$$$, $$$(k_1, k_2, k_2)$$$, $$$(k_1, k_3, k_3)$$$.  two are used in the same triple, one in another: the only case is $$$(i, k, k)$$$, $$$(j, j, j)$$$, $$$j < k$$$. Remove these, add $$$(i, j, j)$$$ and $$$(j, k, k)$$$.  two of them are used in different triples, one not used: $$$(t_1, k_1, k_1)$$$, $$$(t_2, k_2, k_2)$$$, $$$\{t_1, t_2\} \subset \{i, j, j\}$$$, $$$j \le k_1 \le k_2$$$. Remove these triples, replace with $$$(i, j, j)$$$ and $$$(k_1, k_2, k_2)$$$.  two of them are used in the same triple, one not used: the only case is $$$(j, j, j)$$$. Remove this, add $$$(i, j, j)$$$.  one of them in used in some triple, two are not used: $$$(t, k, k)$$$, $$$t \in \{i, j, j\}$$$, $$$j \le k$$$. Remove this, add $$$(i, j, j)$$$.  none of them is used. This is not possible because it is the optimal solution.
• all three are used in different triples: $$$(t_1, k_1, k_1)$$$, $$$(t_2, k_2, k_2)$$$, $$$(t_3, k_3, k_3)$$$, $$$\{t_1, t_2, t_3\} = \{i, j, j\}$$$, $$$j \le k_1 \le k_2 \le k_3$$$. Remove these triples and replace them with $$$(i, j, j)$$$, $$$(k_1, k_2, k_2)$$$, $$$(k_1, k_3, k_3)$$$.
• two are used in the same triple, one in another: the only case is $$$(i, k, k)$$$, $$$(j, j, j)$$$, $$$j < k$$$. Remove these, add $$$(i, j, j)$$$ and $$$(j, k, k)$$$.
• two of them are used in different triples, one not used: $$$(t_1, k_1, k_1)$$$, $$$(t_2, k_2, k_2)$$$, $$$\{t_1, t_2\} \subset \{i, j, j\}$$$, $$$j \le k_1 \le k_2$$$. Remove these triples, replace with $$$(i, j, j)$$$ and $$$(k_1, k_2, k_2)$$$.
• two of them are used in the same triple, one not used: the only case is $$$(j, j, j)$$$. Remove this, add $$$(i, j, j)$$$.
• one of them in used in some triple, two are not used: $$$(t, k, k)$$$, $$$t \in \{i, j, j\}$$$, $$$j \le k$$$. Remove this, add $$$(i, j, j)$$$.
• none of them is used. This is not possible because it is the optimal solution.
• the triple is $$$(j, j, j)$$$. Let's see where these $$$j$$$s are used. They can only be used in three different triples $$$(j, k_1, k_1)$$$, $$$(j, k_2, k_2)$$$, $$$(j, k_3, k_3)$$$, $$$j \le k_1 \le k_2 \le k_3$$$. Remove these triples and replace them with $$$(j, j, j)$$$, $$$(k_1, k_2, k_2)$$$, $$$(k_1, k_3, k_3)$$$.