목마른 소

최근 수위가 크게 변하고 있지만, 물가에 있는 목마른 소가 이를 바꿀 수도 있다!

앞으로 $N$일 동안의 수위가 어떻게 될지에 관한 정보를 받았다. 임의의 날 $i$의 수위는 $a_i$이다. 어떤 날의 수위가 적어도 영이라면 소는 그날의 물을 모두 마실 수 있다. 목마른 소가 임의의 날에 물을 마시게 하면, 소는 탐욕스럽게 물 $a_i$단위를 전부 마신다. 또한 목마른 소가 물을 마시게 하면 그 이후 모든 날의 수위가 $a_i$단위만큼 감소한다. 미래의 날에는 수위가 음수가 될 수도 있으며, 이는 소가 그날에는 물을 전혀 마실 수 없다는 뜻이다.

목마른 소는 몹시 목이 마르므로, $N$일 전체에 걸쳐 가능한 한 많은 물을 마시고 싶어 한다. 물을 마실 날을 최적으로 정했을 때 얼마나 마실 수 있는지 목마른 소가 알아내도록 도와주자.

채점

당신의 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹에는 여러 테스트 케이스가 포함된다. 한 테스트 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$19$| $N, a_i \leq 200$

$2$ |$29$| $N \leq 3000$

$3$ |$52$| 추가 제한 조건 없음.

첫째 줄에는 위에서 설명한 날의 수를 나타내는 정수 $N$이 주어진다 ($1 \leq N \leq 3 \cdot 10^5$).

둘째 줄에는 $N$개의 정수 $a_1, a_2, \dots, a_N$ $(1 \leq a_i \leq 10^9)$이 주어지며, 여기서 $a_i$는 $i$번째 날의 수위를 나타낸다.

목마른 소가 $N$일 전체에 걸쳐 마실 수 있는 물의 최대 단위 수를 정수로 출력한다.

예제 $1$에서 소는 첫날에 물을 마실 수 있다. 그러면 이후 날들의 수위는 $[-5,0]$이 된다. 이는 소가 더 이상 물을 전혀 마실 수 없다는 뜻이다. 따라서 소는 총 $10$단위의 물을 마시며, 이는 최적이다. 다른 최적의 음용 일정도 있으며, $2$일과 $3$일 모두에 물을 마셔도 된다.

예제 $2$에서 물을 마시는 최적의 방법 중 하나는 $2$, $4$, $5$일에 물을 마시는 것이며, 그 결과 소는 물 $10$단위를 마신다. 이 일정을 따르면 수위는 다음과 같다. 각 날에 소가 물을 마신 후(그날 물을 마시는 경우), 이후 날들의 수위를 표시한다.

• $1$일: $[3,2,9,10]$

• $2$일: $[-1,6,7]$

• $3$일: $[6,7]$

• $4$일: $[1]$

• $5$일: $[]$