은행

원더랜드의 월 스트리트에는 은행이 $n$개 있다. 은행은 원형으로 늘어서 있어서 은행마다 왼쪽 이웃과 오른쪽 이웃이 하나씩 있다. 첫 은행의 왼쪽 이웃은 마지막 은행이고, 마지막 은행의 오른쪽 이웃은 첫 은행이다. 은행에는 $0$번부터 $n-1$번까지 번호가 붙어 있고, $i$번 은행의 왼쪽 이웃은 $(i-1+n) \bmod n$번 은행, 오른쪽 이웃은 $(i+1) \bmod n$번 은행이다.

$i$번 은행의 자본은 $k_i$다. 모든 은행의 자본을 더한 값은 양수다.

어떤 은행 $i$의 자본 $k_i$가 음수이면, 은행 요정이 마법 이동을 한 번 써서 그 자본을 양수로 바꾼다. $k_i = -7$이었다면 마법 이동 뒤에는 $k_i = 7$이 된다. 대가는 두 이웃이 치른다. 왼쪽 이웃과 오른쪽 이웃은 각각 자본이 $|k_i|$만큼 줄어든다. 왼쪽 이웃의 자본이 $5$, 오른쪽 이웃의 자본이 $11$이었다면 마법 이동 뒤에는 각각 $-2$와 $4$가 된다.

감소는 이웃 관계마다 따로 적용된다. 그래서 $n = 2$이면 남은 한 은행이 왼쪽 이웃이면서 오른쪽 이웃이므로 자본이 $2|k_i|$만큼 줄어든다. $n = 1$이면 유일한 자본이 양수이므로 마법 이동을 쓸 상황이 생기지 않는다.

모든 은행의 자본을 $0$ 이상으로 만들려면 은행 요정은 마법 이동을 최소 몇 번 해야 하는가?

첫째 줄에 은행의 수 $n$이 주어진다. ($0 < n < 10000$)

둘째 줄에 월 스트리트에 놓인 순서대로 자본 $k_0, k_1, \dots, k_{n-1}$이 공백 하나로 구분되어 주어진다. 각 자본은 $-32000 < k_i < 32000$인 정수이고, 전체 합은 양수다.

마법 이동의 최소 횟수를 한 줄에 출력한다.