Maximum Possible Minimum Power

You are given an integer \(n\) and a list of \(n\) positive integers representing the power values of crystals. You are allowed to perform one ceremony in which you select a contiguous segment (subarray) of crystals and update each crystal in that segment to the floor of their average value. That is, if the chosen subarray has sum \(S\) and length \(L\), then each crystal in the subarray becomes \(\left\lfloor \frac{S}{L} \right\rfloor\). The crystals not included in the ceremony remain unchanged.

Your task is to maximize the minimum power among all crystals after the ceremony. In other words, determine the maximum possible value \(M\) such that after performing the ceremony on an appropriate contiguous subarray, every crystal has a power of at least \(M\).

Note: It is optimal to include every crystal that has a power lower than \(M\) in the ceremony, while those already higher than \(M\) may be left unchanged. In many cases, the best strategy is to apply the ceremony to the entire array, thus increasing the minimum power to \(\left\lfloor \frac{\text{sum of all elements}}{n} \right\rfloor\>.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(n\), representing the number of crystals. The second line contains \(n\) space-separated positive integers, where the \(i\)-th integer represents the power of the \(i\)-th crystal.

outputFormat

Output a single integer to standard output (stdout): the maximum possible minimum power of the crystals after performing exactly one ceremony.

5
1 2 3 4 5

3