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.