Given a sequence of $N$ integers $A = (A_1, A_2, \dots, A_N)$.

You can perform the following operation any number of times: Choose an index $i$ such that $1 \le i < N$ and $A_i > 0$, then replace $A_i$ with $A_i - 1$ and $A_{i+1}$ with $A_{i+1} + 1$.

Find the maximum possible value of the minimum element in the sequence $A$ after performing the operation any number of times.

Input

The first line contains an integer $N$. The second line contains $N$ integers $A_1, A_2, \dots, A_N$.

Output

Output the maximum possible value of the minimum element in the sequence.

Constraints

• $2 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$

Examples

Input 1

3
2 2 2

Output 1

2

Input 2

3
1 2 3

Output 2

2

Input 3

5
10 0 0 0 0

Output 3

0