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

[\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-1]

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

u

예제 입력 1

3
3 1 2

예제 출력 1

1

예제 입력 2

7
4 5 2 2 1 5 8

예제 출력 2

3

힌트

P+1<Q 라면 P<K<Q 인 정수 K가 존재하여</p>

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

이다.