25633번 - 도미노 넘어뜨리기

$N$개의 도미노가 일렬로 세워져 있다. 도미노에는 무게가 존재하는데, $i$번째 도미노의 무게는 $a_i$이다. 단현이는 $N$개의 도미노 중 일부 도미노를 제거할 수 있다. 만약 남은 도미노에서 $i$번째 도미노를 제거하면 $i$번째 도미노의 양옆의 도미노가 이웃하게 된다.

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

일부를 제거하고 남은 $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$이 주어진다. $a_i(1 \le a_i \le 1\ 000\ 000)$는 $i$번째 도미노의 무게이다.

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