30631번 - 렉시오

문제

$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ドル$이 존재한다.

출력

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

제한

힌트