결혼식의 위기

한 유명한 축구 선수가 결혼을 하고 하객들을 위한 파티를 연다. 하객들은 선수 별장 정원에 있는 원형 연못 주변의 테이블에 앉아 있다. 각 테이블에는 정확히 같은 수의 하객이 앉을 수 있고, 연못 주변에서 이웃한 테이블 사이의 거리는 1이다.

전통적인 베스트맨 건배 순간에 위기가 터졌다. 하객 테이블에 있는 샴페인 잔의 총 개수는 정확히 하객 수와 같지만, 잔이 테이블마다 고르게 분포하지 않았을 수 있다. 어떤 테이블에는 하객 수보다 잔이 많고, 어떤 테이블에는 하객 수보다 잔이 적을 수 있다.

잔 분포를 고치는 일을 맡은 웨이터가 한 명 있다. 이 웨이터는 남는 잔을 테이블에서 거두어 잔이 부족한 테이블로 옮긴다. 잔 하나를 고치는 비용은 웨이터가 그 잔을 테이블에 옮겨 줄 때까지 나르는 거리이다. 작업의 총비용은 모든 잔의 비용의 합이다. 웨이터는 어느 테이블에서든 시작할 수 있지만, 선수는 미신을 믿기 때문에 웨이터가 잔 분포를 고칠 때 오직 시계 방향이나 반시계 방향으로만 걸어가도록 허락할 것이다. 즉, 웨이터가 한 방향(시계 방향 또는 반시계 방향)으로 출발하면 방향을 바꿀 수 없다.

축구 선수에게서 사인받은 유니폼을 받고 싶다면, 잔 분포를 고치는 최소 총비용을 구하는 일을 도와주자.

첫째 줄에는 원형 연못 주변의 테이블 수를 나타내는 정수 $N$이 주어진다($1 \le N \le 10^5$). 둘째 줄에는 각 테이블에 있는 잔의 개수를 나타내는 $N$개의 정수 $G_1, G_2, \dots ,G_N$이 주어진다($0 \le G_i \le 1000$ for $i = 1, 2, \dots , N$). 이 수들은 시계 방향 순서로 주어진다. $N$이 $\sum_{i=1}^{N}{G_i}$를 나눈다는 것이 보장된다.

잔 분포를 고치는 최소 총비용을 나타내는 정수를 한 줄에 출력한다.