34472번 - 교도소 서브태스크

문제

태평양 한가운데에 있는 유명한 교도소에는 $N$개의 방이 있다. 각 방은 1ドル$번 방에서 $N$번 방까지 번호가 붙어 있다. 각 $i$ (1ドル \le i < N$)에 대해 $i$번 방에서 $i+1$번 방으로 이동할 수 있는 통로가 존재하고, $N$번 방에서 1ドル$번 방으로 이동할 수 있는 통로가 존재한다. 단방향 통로이므로 통로를 통해 반대 방향으로 이동할 수는 없다.

현재 $i$번 방에는 $A[i]$명이 수감되어 있다. 모든 방의 수감자의 수를 합하면 $N$의 배수가 된다.

당신은 모든 방에 있는 수감자의 수를 동일하게 만들려고 한다. 이를 위해, 몇 명의 수감자를 통로를 통해 다른 방으로 이동시킬 것이다. 이때, 각 수감자가 통로를 통해 이동하는 횟수를 모두 합한 값을 최소화하고 싶다.

입력

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에 $A[1], \cdots, A[N]$이 공백을 사이에 두고 주어진다.

출력

각 수감자가 통로를 통해 이동하는 횟수를 모두 합한 값의 최솟값을 출력하라.

제한

• 2ドル \le N \le 500,000円$
• 0ドル \le A[i] \le 1,000円,000円,000円$
• $A[1] + \cdots + A[N]$은 $N$의 배수이다.

서브태스크

힌트