시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 153 22 11 24.444%

문제

월스트리트에는 n개의 은행이있다. 모든 은행은 양 옆으로 이웃하는 은행이 하나씩 있으며, 첫번째 은행의 왼쪽에는 마지막 은행이있고, 마지막은행의 오른쪽에는 첫번째 은행이있다(원형으로 나열되있다). 각 은행은 K만큼의 자본이 있고 모든 은행 자본의 합은 양수이다.

i번 은행의 자본, K(i)가 음수일 경우, 은행 요정은 이 자본을 양수로 만들어줄수있다. 예를들어, 자본이 -7일경우, 요정의 힘을 빌린 후에는 자본이 7이된다. 그러나 요정의 힘을 사용하면 이웃하는 양 옆 은행은 i은행 자본의 절댓값만큼 손해를 본다. i은행의 양옆 이웃은행의 자본이 5와 11이라면 -2와 4로 줄어든다.

모든 은행의 자본을 0 또는 양수로 만들기 위해 요정의 힘을 빌려야할 최소 횟수는 얼마일까?

입력

첫번째 줄에는 은행 갯수 n이 주어진다. (0 < n < 10000)

두번째 줄에는 각 은행의 자본 k(i)가 순서대로 주어진다. (-32000 < k(i) < 32000)

각 자본은 한칸의 공백을 두고 주어진다.

출력

요정의 힘을 빌려야할 최소 횟수를 출력한다.

예제 입력

4
1 -2 -1 3

예제 출력

9

힌트