시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB46416913943.849%

문제

서울과학고 기숙사에는 $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$의 배수입니다.

서브태스크

번호배점제한
19

모든 $A_i$가 동일하다.

216

$A_i$들 중 최빈값은 $N-1$회 이상 등장한다.

335

$1 \le N \le 100$, $1 \le A_i \le 100$

440

추가 제한 조건이 없다.

예제 입력 1

3
1 3 2

예제 출력 1

1

예제 입력 2

7
2 6 3 2 5 4 6

예제 출력 2

10

출처

High School > 서울과학고등학교 > 2022 SciCom Qualification Test B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.