P15989 [PA 2026] Amber / Bursztyny

After each storm, the Bajtoćka beach is covered with amber. This is because the Bajtoćkie Sea was formed on the site of an ancient forest; resin solidified into amber and was washed onto the beach during storms. The beach is divided by breakwaters into $n$ sections. The waves in Bajtoćkie storms have an interesting property: every wave has the same width, and each wave delivers exactly one piece of amber to each of $k$ consecutive sections of the beach. Yesterday evening Bajtazar took a walk on the beach. Unfortunately, by then all the amber had already been picked up. Luckily, a storm happened during the night, so Bajtazar got up early in the morning and rushed to the beach. He managed to count how many pieces of amber the waves washed onto each section. Bajtazar wants to know what the maximum possible wave width $k$ was during this storm. Please help him compute it.

The first line of input contains an integer $n$ ($1 \le n \le 100000$), the number of sections the beach is divided into. The second line contains $n$ integers $a_1, \ldots, a_n$ ($0 \le a_i \le 1000000$), where $a_i$ is the number of pieces of amber in the $i$-th section of the beach. You may assume that at least one $a_i$ is positive.

Output one integer $k$, the maximum wave width consistent with the given amber distribution.

### Sample Explanation In the first sample test, the amber distribution can be produced by eight waves of width $k = 3$: ::::align{center}  :::: The same distribution can also be produced by waves of width $2$ or $1$. In the second sample test, waves of width $2$ are impossible, because each such wave has only one way to be placed on the beach, namely adding one piece of amber to each of two sections. Translated by ChatGPT 5