33577번 - 8번 출구

문제

2024년 5월, 꽃다운 봄의 어느 아름다운 날, ecode는 급식실 앞 계단에서 굴러떨어져 잠시 기절했다. 시간이 얼마나 지났을까? ecode가 눈을 뜨자 8번 출구라는 비디오 게임 세계 안이었다. 8번 출구는 이변이 잔뜩 일어나는 $N$개의 출구를 지나쳐 밖으로 탈출해야 하는 게임이다. 출구 하나를 지나기 위해서는 출구에서 방출되는 이변력(異變力)을 이겨낼 수 있는 충분한 면역력이 필요하다.

ecode가 갇혀 있는 게임은 1ドル$번 출구부터 $N$번 출구까지 존재한다. $i$번 출구를 통과하면 $A_i$만큼 면역력이 감소하고 $i+1$번 출구로 이동한다. $N$번 출구를 통과하면 비디오 게임을 탈출할 수 있다. $i$번 출구를 통과하기를 포기하면 면역력이 $A_i$만큼 증가하고 1ドル$번 출구로 돌아간다. 보유한 면역력은 어떤 상황에서도 음수가 되어서는 안 된다.

ecode는 1ドル$번 출구에서 면역력 0ドル$을 가지고 시작한다. ecode가 $N$번 출구를 통과하여 탈출하기 위해서 최소 몇 번 1ドル$번 출구로 돌아가야 하는지 구하시오.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \leq N \leq 10^5)$

두 번째 줄에 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분하여 주어진다. $(1 \leq A_1, A_2, \dots, A_N \leq 10^9)$

출력

ecode가 $N$번 출구를 통과하여 탈출하기 위해 최소 몇 번 1ドル$번 출구로 돌아가야 하는지 출력한다.

제한

노트

'8번 출구'는 원래 이런 비디오 게임이다.

급식실 사건은 실화를 바탕으로 작성되었다.