Ferris Wheel Gondola Rebalancing

MediumArrayGreedySortingCircular arrayMedianPrefix sum2 sample tests5 hidden tests

A traveling carnival's Ferris wheel has n gondolas bolted to the rim, numbered 1 through n in clockwise order; gondola n sits directly beside gondola 1, so the ring wraps around. Gondola i currently holds a_i riders. While the wheel is paused for boarding, an attendant may ask exactly one rider to step from their gondola into whichever of its two immediate ring-neighbors they choose — this counts as one transfer. The ride cannot start until every gondola holds exactly the same number of riders (the total rider count is guaranteed to be a multiple of n, so an even split is always achievable). Find the minimum number of transfers the attendant must arrange.

Input format

Line 1: a single integer n, the number of gondolas.
Line 2: n space-separated integers a_1, a_2, ..., a_n, the current number of riders in each gondola, in clockwise order.

Output format

A single integer: the minimum number of transfers needed so every gondola holds the same number of riders.

Constraints

3 <= n <= 200000
0 <= a_i <= 1000000
The sum of all a_i is divisible by n.

Examples

Example 1

Input

4
1 2 3 2

Expected

Explanation

The target load is (1+2+3+2)/4 = 2 riders per gondola. Gondola 1 needs one more rider and gondola 3 has one rider too many; the shortest path around the ring between them is 2 hops (through either gondola 2 or gondola 4), so moving that single extra rider along either path costs exactly 2 transfers. Gondolas 2 and 4 are already at the target, so the answer is 2.

Example 2

Input

5
0 0 0 0 10

Expected

Explanation

Gondola 5 holds all 10 riders while the other four are empty, so the target is 10/5 = 2 riders each. Gondola 5 sends 2 riders directly to each of its two neighbors, gondolas 4 and 1, costing 2 transfers per rider, i.e. 4 transfers to each neighbor (8 total). The two gondolas across the ring, 2 and 3, each still need 2 riders that must travel 2 hops through a neighbor, costing 2 x 2 = 4 transfers per gondola (8 total). Overall that is 4 transfers to reach gondolas 1 and 4 combined... recomputing carefully: 2 riders to gondola 4 costs 2 transfers, 2 riders to gondola 1 costs 2 transfers, 2 riders to gondola 3 (2 hops each) costs 4 transfers, and 2 riders to gondola 2 (2 hops each) costs 4 transfers, for a total of 2+2+4+4 = 12.

Ready to solve this?