주식 투자

배찌가 $N$ 일 동안의 주식 투자로 얻은 이익이 날짜 순서대로 $A_1, A_2, \cdots, A_N$이라고 한다. 시작부터 $i$ 번째 날짜까지의 이익 $P_i$는 $A_1 + A_2 + \cdots + A_i$로 정의된다.

넥슨이 최근에 개발한 과거 지우기 장치는 과거의 어떤 날짜의 투자 결과를 무효로 만들 수 있다. 즉, 한 번의 장치 사용으로 한 $A_i$를 $0$으로 만들 수 있는 것이다. 이 장치를 사용하는 비용은 너무나 많이 들어서 이익이 음수인 날짜를 모두 무효로 하는 것은 비효율적일 수 있다.

배찌는 최소한 모든 $P_i$가 $0$ 이상이 되도록 하고 싶다. 비용을 최대한 줄이기 위해 과거 지우기 장치를 이용하는 횟수를 최소화하고 싶다.

$A_1, A_2, \cdots, A_N$를 입력으로 받아 모든 $P_i$가 $0$ 이상이 되게 과거 지우기 장치를 이용하는 최소 횟수를 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 날짜 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 200\, 000$)

두 번째 줄에 $A_1, A_2, \cdots, A_N$를 나타내는 $N$ 개의 정수가 공백으로 구분되어 주어진다. 주어지는 $A_i$는 $-10^9$ 이상 $10^9$ 이하이다.

출력 형식

첫 줄에 모든 $P_i$를 $0$ 이상이 되도록 과거 지우기 장치를 이용하는 최소 횟수를 출력한다.

예제

5
-2 3 -5 -1 6

2

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설