Equalizing Water in Glasses

Bitoasia lined up several glasses in a row and poured the same amount of water into every one of them, then stepped out to the bathroom. While she was away, Bajtokozik sneaked into the room and, as a prank, quickly poured water back and forth between the glasses.

When Bitoasia came back and saw that the glasses now held uneven amounts of water, she was very upset and ran off crying to Bitomama. An investigation turned up no culprit, so there was nothing left to do but pour the water around again until every glass holds the same amount.

Bitoasia wants to finish with as few moves as possible so she does not tire herself out. In a single move she picks one glass and pours some water (any amount she likes) into an adjacent glass, the one immediately to its left or right. Determine the minimum number of moves she needs.

You may assume that a single glass can hold all the water from every glass combined. At the start each glass held the same whole number of units of water. Bajtokozik never spilled a drop outside the glasses and no water evaporated, so the total amount of water is unchanged.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of glasses in the row. The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10^6$), where $w_i$ is the number of units of water in the $i$-th glass after Bajtokozik's prank. The total amount of water is always divisible by $n$, so the glasses can be equalized with a whole number of units in each.

Print one integer: the minimum number of moves Bitoasia needs so that every glass holds the same amount of water.