34049번 - 배열 나누기

문제

길이 $N$의 정수 배열이 주어진다. 당신은 주어진 배열을 여러 개의 연속한 부분 배열로 나눌 수 있다. 단, 나뉜 부분 배열들은 다음 조건을 만족해야 한다.

• 배열의 길이를 $L$이라고 할 때, 1ドル \leq i \leq L$을 만족하는 모든 정수 $i$에 대해, 1ドル$번째부터 $i$번째 원소까지의 합은 항상 0ドル$ 이상이어야 한다.

조건을 만족하도록 부분 배열을 나눌 때, 나뉜 부분 배열의 최대 개수를 구하여라.

입력

첫 번째 줄에 배열의 원소의 개수 $N$이 주어진다. $(1 \leq N \leq 200,000円)$

두 번째 줄에 $N$개의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-200,000円 \leq A_i \leq 200,000円)$

입력으로 주어지는 모든 수는 정수이다.

출력

조건을 만족하도록 부분 배열로 나누는 방법이 없다면 -1, 있다면 나뉜 부분 배열의 최대 개수를 출력한다.

제한

힌트