도미노 넘어뜨리기

문제

$N$개의 도미노가 일렬로 세워져 있다. 도미노에는 무게가 존재하는데, $i$번째 도미노의 무게는 $a_i$이다. 시온이는 $N$개의 도미노 중 일부 도미노를 제거할 수 있다. 만약 $i$번째 도미노를 제거하면 $i - 1$번째 도미노와 $i + 1$번째 도미노가 이웃하게 된다.

시온이는 이렇게 일부를 제거하고 남은 $M$개의 도미노가 완벽하게 나열되도록 만들고 싶다. 도미노가 완벽하게 나열되었다는 것은, 나열된 도미노에서 첫 번째 도미노를 넘어뜨렸을 때 마지막 도미노까지 차례로 넘어진다는 것을 의미한다.

일부를 제거하고 남은 $M$개의 도미노에서 $j$번째 도미노의 무게를 $b_j$라고 할 때, $j(2 \le \ j \le M)$번째 도미노가 넘어지기 위해서는 첫 번째 도미노부터 $j - 1$번째 도미노까지 모두 넘어져야 하고, 넘어진 도미노의 무게를 합한 값이 $b_j$보다 같거나 커야한다.

시온이는 $N$개의 도미노에서 일부 도미노를 제거해서 완벽하게 나열되도록 만들고 싶다. 완벽하게 나열할 수 있는 도미노의 최대 개수는 얼마일까?

입력

첫째 줄에 도미노의 개수 $N(1\le N \le 1\ 000)$이 주어진다.

둘째 줄에 도미노의 무게를 의미하는 정수 $a_1, a_2, ... , a_N (1 \le a_i \le 1\ 000\ 000)$이 주어진다.

출력

완벽하게 나열할 수 있는 도미노의 최대 개수를 출력한다.

예제 입력 1

5
2 1 6 5 4

예제 출력 1

3

무게가 $2$인 도미노와 $1$인 도미노를 제거해서 $[6, 5, 4]$로 나열하면 된다.

예제 입력 2

4
3 1 2 6

예제 출력 2

4

아무 도미노도 제거하지 않고 $[3,1,2,6]$으로 나열하면 된다.

예제 입력 3

3
1 2 3

예제 출력 3

1