마이너스 통장

면접 대비

시간 제한1초메모리 제한1024 MB

요약

입금과 출금이 순서대로 주어질 때, 잔액이 한 번도 음수가 되지 않도록 하는 최소의 음이 아닌 시작 잔액을 구한다.

난이도: 쉬움10점 중 3점
유형: 누적 합, 구현, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

은행은 계좌 잔액보다 많은 금액을 출금하려고 하면 마이너스 통장 수수료를 부과하는 경우가 많다. 입금과 출금이 순서대로 주어질 때(각 입금과 출금은 즉시 잔액에 반영된다고 가정한다), 이 순서 전체에서 마이너스 통장 수수료를 한 번도 물지 않으려면 처음에 필요한 최소 잔액(음이 아닌 정수)을 구하시오.

입력

첫째 줄에는 거래의 수를 나타내는 정수 $n$ 이 주어진다( $1 \le n \le 1{,}000$ ).

다음 $n$ 개 줄에는 각 줄마다 정수 $t$ 가 하나씩 주어진다( $-10^6 \le t \le 10^6$ , $t \neq 0$ ). 이 값들은 거래가 일어나는 순서대로 주어진다. 양수는 입금, 음수는 출금을 나타낸다. 두 거래가 동시에 일어나는 경우는 없다.

출력

마이너스 통장 수수료를 피하기 위해 계좌에 처음부터 있어야 하는 최소 잔액(음이 아닌 정수)을 한 줄에 출력한다.

예제1

예제 1
입력
```
3
3
-5
3
```
예상 출력
```
2
```