25637번 - 회전 목마

회전 목마는 회전하는 원판의 가장자리에 위치한 목마를 타고 여러 바퀴를 도는 놀이기구이다. ANA 놀이공원의 회전 목마는 $N$개의 목마로 구성되어 있는데, 목마는 시계 방향으로 $1$번부터 $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$이다.

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