Array modification

★★★★★

3.5

41 votes

Algorithms, Dynamic Programming, Greedy Algorithms

Details

Problem

M as a prisoner loves playing with his array $a_1, a_2, ..., a_n$ , he can do following operation as much as he wants:

Choose two integers $i, j$ that $1 \leq i,j \leq n$ and $|i-j| = 1$ and also $a_i \ge 2$ .
Then add 1 to $a_j$ ( $a_j = a_j+1$ ) and subtract 2 from $a_i$ ( $a_i = a_i - 2$ ).

M thinks beautifulness of an array is maximum value of it ( $max(a_1, a_2, ..., a_n)$ ).

What is the maximum value of beautifulness that M can get after doing above operation as much as he wants?

Input

First line contains only $n$ , length of array.

Second line contains the array elements $a_1, a_2, ..., a_n$ separated by space.

$2 \leq n \leq 2 \times 10^5$

$1 \leq a_i \leq 10^9$

Output

The only line of output contains an integer, maximum beautifulness value that M can get.

Time Limit: 1.5

Memory Limit: 256

Source Limit:

Explanation

M can do the operation on $i=1, j=2$ then on $i=2, j=3$ then on $i=5, j=4$ and then on $i=4, j=3$ .

After operations array becomes $1, 1, 6, 1, 1$ .