The Bajtocka beach is full of amber after every storm. This is because the Bajtockie Sea was formed on the site of an ancient forest; the resin solidified, creating amber, which is washed up on the beach during storms. The beach is divided by breakwaters into $n$ segments. Waves during a Bajtockie storm have an interesting property: each of them has the same width and delivers one piece of amber to exactly $k$ consecutive beach segments.

Bajtazar took a walk on the beach yesterday evening. Unfortunately, all the amber had already been collected by then. Fortunately, there was a storm at night, so Bajtazar woke up early in the morning and ran to the beach as quickly as possible. He managed to count all the amber pieces washed up by the sea in each of the segments. Bajtazar is wondering what the maximum width $k$ of the waves during the storm could have been. Help him calculate it!

Input

The first line of input contains a single integer $n$ ($1 \le n \le 100\,000$), representing the number of segments the beach is divided into.

The second line contains a sequence of $n$ integers $a_1, \dots, a_n$ ($0 \le a_i \le 1\,000\,000$), representing the number of amber pieces in each beach segment. You may assume that at least one value $a_i$ is positive.

Output

Output a single integer $k$ — the maximum wave width that fits the distribution of the amber.

Examples

Input 1

8
1 2 3 4 5 5 3 1

Output 1

3

Note

In the first example test case, the arrangement of amber could have been obtained by eight waves of width $k = 3$:

Diagram showing the distribution of amber pieces across segments for waves of width 3.

The same arrangement could also have been created by waves of width 2 or 1.

Input 2

2
1 3

Output 2

1

Note

In the second example test case, it could not have been waves of width 2, because each such wave fits on the beach in only one way, adding one piece of amber to both segments.