문제

회전 목마는 회전하는 원판의 가장자리에 위치한 목마를 타고 여러 바퀴를 도는 놀이기구이다. ANA 놀이공원의 회전 목마는 $N$개의 목마로 구성되어 있는데, 회전 목마가 정상적으로 운행하기 위해서는 정확히 $N$명의 손님만을 놀이기구 안에 입장시키고, 한 목마에 정확히 한 사람이 탑승해야한다.

ANA 놀이공원의 안전 관리 요원인 시온이는 회전 목마 안에 정확히 $N$명의 손님을 입장시키는 것에는 성공했지만, 한 목마에 정확히 한 사람이 탑승하게 하는데에는 실패했다. 어떤 목마에는 아무도 탑승하지 않았고, 어떤 목마에는 $2$명 이상의 손님이 탑승해있었다. 다행히도 시온이는 목마에 탑승해 있는 어떤 손님을 인접한 목마로 옮길 수 있다. 이 때, 목마는 원형으로 배치되어있는 것에 유의하자.

모든 목마에 정확히 한 사람이 탑승하게 만들기 위해서는 손님을 최소 몇 번 옮겨야 할까?

입력

첫째 줄에 목마의 개수 $N(3\le N \le 2\,000)$이 주어진다.

둘째 줄에 정수 $a_1, a_2, ..., a_N$이 주어진다. $a_i(0 \le a_i \le N)$는 $i$번 목마에 탑승한 사람의 수이다. 목마에 탑승한 사람의 수의 합은 $N$이다. 즉 $\displaystyle\sum_{i=1}^{N}a_i = N$이다.

출력

모든 목마에 정확히 한 사람이 탑승하게 만들기 위해서는 손님을 최소 몇 번 옮겨야 하는지 출력한다.

예제 입력 1

4
2 2 0 0

예제 출력 1

2

예제 입력 2

5
3 0 2 0 0

예제 출력 2

3