ICPC 대회를 성공적으로 마친 포닉스는 그간 자신을 도와준 사람들과 같이 단체여행을 가기로 했다. 포닉스를 포함한 $N$명의 사람이 같이 다녔으며, 여행 중 발생하는 경비는 매 결제마다 누군가 나서서 $N$인분의 비용을 한번에 계산했다. 즐거운 여행이 끝났고 이제 정산을 할 시간이다!

각 사람에게는 $1$번부터 $N$번까지 번호가 부여되어 있으며, 여행동안 각각 $A_1, A_2, \cdots , A_N$원의 금액을 결제했다. 참고로 매 결제마다 $N$인분을 질렀기 때문에 각 $A_i$는 $N$의 배수이다.

국제적으로 가장 잘 알려진 정산법은 $N$빵으로, 이는 여행을 간 인원들이 적절하게 돈을 서로에게 주고받아 사용한 돈을 모두 같게 만드는 방법이다. 하지만 마구잡이로 돈을 주고받다보면 혼란스러운 법. 포닉스는 질서있는 정산을 위해 아래의 규칙을 정했다.

• $2 \le i \le N-1$에 대해, $i$번 사람은 $i-1$번, $i+1$번 사람과만 돈을 주고받을 수 있다. 또한 $1$번 사람과 $N$번 사람도 돈을 주고 받을 수 있다.

돈을 주고받는 일은 매우 귀찮은 일이기에, 포닉스는 위 규칙에서 사람들 간 주고 받아야 할 금액을 직접 정해 사람들 간 총 송금 횟수가 최소가 되도록 하고 싶다. 포닉스를 도와 정산을 완료하기 위한 가장 적은 송금 횟수가 얼마인지 구해주자!

여행을 갔던 사람들은 모두 잔고가 충분해 정산 과정에서 돈이 부족한 일이 발생하지 않으며, 이 전제에서 유한번의 송금으로 정산을 완료할 수 있음을 증명할 수 있다.

입력 형식

첫째 줄에 여행을 간 인원수 $N$이 주어진다. ($1 \le N \le 500\ 000$)

둘째 줄에 $N$개의 정수 $A_1, A_2, ... , A_N$이 공백으로 구분되어 주어진다. 각 $A_i$는 $0$ 이상 $10^{12}$ 이하의 $N$의 배수이다.

출력 형식

정산 완료를 위한 최소한의 송금 횟수를 출력하여라.

예제

예제 1

입력

5
15 5 20 35 25

출력

3