렉시오

$N$명의 사람들이 "렉시오"라는 보드게임을 즐기고 있다. 참가자들은 일렬로 앉아 있으며, 왼쪽의 참가자부터 차례대로 $1, 2, \cdots, N$번으로 번호가 매겨진다.

렉시오는 매 턴 모든 사람이 카드를 같은 개수로 나눠 갖는다. 각자 가진 카드를 규칙에 따라 제거하다가 누군가 자신의 카드를 모두 제거하면 그 턴이 끝나고 점수를 정산한다. 원하는 만큼 턴을 즐기고 최종 점수가 가장 높은 사람이 승리한다. 한 턴의 점수를 정산하는 방식이 독특하다.

각 턴이 끝날 때 자신보다 카드가 적은 사람이 있으면 그 사람에게 카드 개수의 차이만큼 점수를 전달한다. 따라서 점수가 같은 쌍을 제외한 모든 쌍의 참가자들이 점수를 주고받게 된다. 규칙대로 점수를 정산하면 전달 횟수가 워낙 많아서, 사람들은 정산 방식을 최적화하려고 한다. 사람들은 다음 네 가지 조건을 모두 만족하는 정산 방식을 좋은 정산 방식이라고 부르기로 했다.

1. 결과적으로 각 참가자가 얻거나 잃은 점수는 규칙에 따라 직접 점수를 주고받았을 때와 같아야 한다.
2. 임의의 한 참가자가 이웃한 참가자에게 점수를 전달하는 것이 가능하다.
3. 참가자 한 쌍을 골라서 한 참가자가 다른 참가자에게 점수를 전달할 수 있다. 이런 전달은 전체 정산 과정에서 최대 한 번 가능하다.
4. 위 조건들을 만족하면서 점수를 전달하는 행위를 최소화해야 한다. 다시 말해서, 조건을 만족하면서 점수를 전달하는 행위가 더 적은 정산 방식이 있으면 좋은 정산 방식이 아니다.

예를 들어 $A$, $B$, $C$의 $3$명이 렉시오를 해서 턴이 종료했다고 하자. 턴이 끝나고 남은 카드가 각각 $10$, $5$, $0$개라면 $A$는 $B$에게 $5$점, $C$에게 $10$점을 줘야 하고, $B$는 $C$에게 $5$점을 줘야 한다. $1$번 항목에 따라 어떤 과정을 통해서 전달하든 $A$는 $15$점을 잃고, $B$는 점수를 잃지 않으며, $C$는 $15$점을 얻기만 하면 된다.

$A$, $B$, $C$가 순서대로 앉아 있을 때, $A$가 $B$에게 $15$점을 주고 $B$가 $C$에게 $15$점을 주면 점수를 $2$번 전달해서 정산을 마칠 수 있다.

그런데 $3$번 항목에 쓰인 대로 참가자 쌍 $(A, C)$를 선택해 $A$가 $C$에게 $15$점을 전달하면 한 번에 점수를 정산할 수 있다. 이보다 적은 횟수로는 정산할 수 없으므로, $3$번 항목에 따른 좋은 정산 방식은 한 번에 점수를 정산하는 방식이 된다.

턴이 끝나고 남아 있는 카드의 개수가 참가자들이 앉아 있는 순서대로 주어질 때, 좋은 정산 방식의 점수 전달 횟수를 구해보자.

첫째 줄에 게임에 참가하는 참가자 수를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 1\,000\,000$)

둘째 줄에는 왼쪽으로부터 $i$번 참가자의 해당 턴에 남은 카드의 개수를 $a_i$라고 할 때, $a_1$부터 $a_N$까지 차례대로 공백으로 구분되어 주어진다. ($0 \le a_i \le 1\,000\,000$)

게임의 한 턴은 누군가 카드를 전부 소모한 순간에 종료하므로, 입력에는 반드시 단 한 개의 $0$이 존재한다.

문제의 조건에 따라 좋은 정산 방식의 점수 전달 횟수를 첫째 줄에 출력한다.