교도소

태평양 한가운데에 있는 유명한 교도소에는 $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$의 배수이다.