14922번 - 부분평균

A를 길이 N인 양의 정수로 구성된 배열이라고 하자.(N>2) 정수 P, Q(0<=P<Q<N) 에 대해서 A의 부분평균 A(P, Q)를 다음과 같이 정의하자.

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

예를 들어 주어진 배열 A의 길이가 3이고

A[0]=3, A[1]=1, A[2]=2

라고 하면 A의 가능한 모든 부분평균은 다음과 같다.

A(0,1) = (3+1)/2 = 2

A(0,2) = (3+1+2)/3=2

A(1,2) = (1+2)/2=1.5

위와 같은 경우, 모든 부분평균 중  최소값은 A(1,2)=1.5이다. 그렇다면 주어진 조건을 만족하는 임의의 배열 A가 주어지면 A의 부분평균 중 최소값을 가지는 것을 A(u,v) 라고 할 때, u를 출력하는 프로그램을 작성하라. (답이 여러 개일 경우 가장 작은 u의 값을 출력한다.)

N

A[0], A[1], ..., A[N]

2 ≤ N ≤ 1,000,000, 0 ≤ A[i] ≤ 7×10⁸

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

이다.