부분평균

길이가 $N$인 배열 $A$가 있다. 배열의 인덱스는 0부터 시작한다. $0 \le P < Q < N$을 만족하는 정수 $P$, $Q$에 대해 $A$의 부분평균 $A(P, Q)$를 다음과 같이 정의한다.

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

즉 부분평균은 연속한 두 개 이상의 원소를 뽑아 구한 평균이다.

예를 들어 $N = 3$이고 $A[0] = 3$, $A[1] = 1$, $A[2] = 2$이면 가능한 부분평균은 $A(0, 1) = 2$, $A(0, 2) = 2$, $A(1, 2) = 1.5$ 세 가지이고 이 중 최솟값은 $A(1, 2) = 1.5$이다.

배열 $A$가 주어질 때, 부분평균이 최소인 $A(u, v)$를 찾아 $u$를 출력하는 프로그램을 작성하라. 최솟값을 주는 쌍이 여러 개이면 $u$가 가장 작은 것을 출력한다.

첫째 줄에 배열의 길이 $N$이 주어진다. 둘째 줄에 $A[0]$, $A[1]$, $\dots$, $A[N-1]$이 공백으로 구분되어 주어진다.

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

첫째 줄에 $u$를 출력한다.

$P + 1 < Q$이면 $P < K < Q$인 정수 $K$가 존재해서 다음 두 부등식 중 하나가 성립한다.

$\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}$

또는

$\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}$