Minimum subarray average

You are given an array $A$ of length $N$ whose indices start at 0. For two integers $P$ and $Q$ with $0 \le P < Q < N$, the subarray average $A(P, Q)$ is defined as

$A(P, Q) = \frac{\sum_{i=P}^{Q} A[i]}{Q - P + 1}$

so a subarray average is the average of two or more consecutive elements.

For example, if $N = 3$ with $A[0] = 3$, $A[1] = 1$, $A[2] = 2$, the possible subarray averages are $A(0, 1) = 2$, $A(0, 2) = 2$, and $A(1, 2) = 1.5$. The smallest of them is $A(1, 2) = 1.5$.

Given the array $A$, find a pair $(u, v)$ whose subarray average $A(u, v)$ is minimal and print $u$. If several pairs reach the minimum, print the smallest $u$.

The first line contains the length $N$ of the array. The second line contains $A[0]$, $A[1]$, $\dots$, $A[N-1]$ separated by spaces.

• $2 \le N \le 1{,}000{,}000$
• $0 \le A[i] \le 7 \times 10^8$

Print $u$ on the first line.

If $P + 1 < Q$, then there is an integer $K$ with $P < K < Q$ such that

$\frac{\sum_{i=P}^{K} A[i]}{K - P + 1} \le \frac{\sum_{i=P}^{Q} A[i]}{Q - P + 1} \le \frac{\sum_{i=K+1}^{Q} A[i]}{Q - K}$

or

$\frac{\sum_{i=K+1}^{Q} A[i]}{Q - K} \le \frac{\sum_{i=P}^{Q} A[i]}{Q - P + 1} \le \frac{\sum_{i=P}^{K} A[i]}{K - P + 1}$