키트 분배하기

서울과학고 기숙사에는 $N$개의 방이 일렬로 나열되어 있습니다. 교사들은 교내 방역을 위해 각 방에 진단 키트를 제공했습니다.

그러나 분배 과정에서 실수가 있어 방마다 받은 키트의 수가 달라졌습니다. 구체적으로 $i$번 방이 받은 키트의 수는 $A_i$개입니다. 학생들은 이 상황을 해결하려고 키트를 서로 주고받기로 했습니다.

멀리 떨어진 방끼리 키트를 주고받으면 소란스러우므로, 키트는 인접한 방끼리만 주고받을 수 있습니다. 한 방에서 인접한 다른 방으로 키트 한 개를 건넬 때마다 혼잡도가 1 증가합니다. 키트가 없는 방은 다른 방으로 키트를 건넬 수 없습니다.

혼잡도가 너무 높으면 학생들이 벌점을 받을 수 있습니다. 그래서 학생들은 혼잡도를 최소로 하면서 모든 방이 같은 수의 키트를 갖도록 하려고 합니다. 이 목표를 달성하는 데 필요한 혼잡도의 최솟값을 구하시오. 전체 키트의 수는 방의 수의 배수임이 보장됩니다.

첫 줄에 방의 개수를 나타내는 정수 $N$이 주어집니다.

다음 줄에는 각 방이 처음에 받은 키트 수를 나타내는 정수 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 주어집니다.

최소 혼잡도를 출력합니다.

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^6$
• 모든 정수 $i$ ($1 \le i \le N$)에 대해, $A_i$의 합은 $N$의 배수입니다.