https://www.acmicpc.net/board/...

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

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

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

입력

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

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

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

출력

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