물컵의 물 균등하게 만들기

비토아시아는 물컵 여러 개를 한 줄로 놓고 각 컵에 같은 양의 물을 부은 뒤 화장실에 다녀왔습니다. 그 사이 바이토코지크가 몰래 방에 들어와 장난을 치려고 컵들 사이로 물을 이리저리 옮겨 부었습니다.

돌아온 비토아시아는 컵마다 물의 양이 제각각인 것을 보고 크게 속상해하며 울면서 비토엄마에게 달려갔습니다. 하지만 아무리 조사해도 범인을 찾지 못했고, 결국 다시 물을 옮겨 부어 모든 컵의 물 양을 똑같이 맞추는 수밖에 없었습니다.

비토아시아는 너무 지치지 않도록 되도록 적은 횟수로 끝내고 싶습니다. 한 번의 이동은 컵 하나를 골라 그 컵의 물을 원하는 만큼 바로 옆(왼쪽 또는 오른쪽) 컵으로 부어 옮기는 것입니다. 필요한 최소 이동 횟수를 구하세요.

컵 하나에는 모든 컵의 물을 합쳐도 다 담을 수 있다고 가정합니다. 처음에 모든 컵에는 같은 정수 단위의 물이 들어 있었고, 바이토코지크가 물을 옮기는 동안 컵 밖으로 흘린 물도 증발한 물도 없으므로 전체 물의 양은 그대로입니다.

첫째 줄에 한 줄로 놓인 컵의 개수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다. 둘째 줄에는 $n$개의 정수 $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10^6$)이 주어지며, $w_i$는 바이토코지크의 장난 이후 $i$번째 컵에 담긴 물의 단위 수입니다. 전체 물의 양은 항상 $n$으로 나누어떨어지므로, 각 컵의 물을 정수 단위로 똑같이 맞출 수 있습니다.

모든 컵의 물 양이 같아지도록 하는 데 필요한 최소 이동 횟수를 정수 하나로 출력합니다.