키트 분배하기

서울과학고 기숙사에는 $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$
• $1 \le i \le N$인 모든 정수 $i$에 대해, $A\_i$의 합은 $N$의 배수입니다.