우리의 어린 친구 Askhat은 흥미로운 현상을 발견했습니다. 점점 커지는 합을 가진 "점프"로 배열을 덮으려는 시도가 생각만큼 간단하지 않을 수 있다는 것입니다. 물론, 이제 여러분은 이를 수행하는 방법을 찾아야 합니다.

길이가 $N$인 양의 정수 수열이 주어집니다. 주어진 수열을 다음 조건을 만족하도록 최대 개수의 구간으로 나누십시오.

1. 수열의 모든 원소는 정확히 하나의 구간에 속해야 합니다.
2. 첫 번째 구간을 제외한 모든 구간의 합은 이전 구간의 합보다 작지 않아야 합니다.

입력

첫 번째 줄에는 정수 $N$ ($1 \le N \le 5 \cdot 10^5$)이 주어집니다. 다음 줄에는 $N$개의 양의 정수 $a_i$ ($1 \le a_i \le 10^9$)가 공백으로 구분되어 주어집니다.

출력

주어진 수열을 나눌 수 있는 최대 구간 개수를 하나의 정수로 출력하십시오.

서브태스크

이 작업은 추가 제약 조건이 있는 5개의 서브태스크로 구성됩니다.

1. $1 \le N \le 20$, $a_i \le 10^6$. 13점.
2. $1 \le N \le 500$. 14점.
3. $1 \le N \le 3000$. 10점.
4. $1 \le N \le 10^5$. 36점.
5. 원래 제약 조건. 27점.

예제

입력 1

4
2 3 1 7

출력 1

3

입력 2

5
6 2 3 9 13

출력 2

3

입력 3

3
3 1 2

출력 3

2