Supply Strategy timer 1s memory 512MB

Jungol's base is in a perfect circular shape.

Inside the base, there are N rooms numbered 1 to N in clockwise order along the perimeter.

Each room has doors leading to two adjacent rooms and a door leading to the outside.

Jungol's supply officer wants exactly A_i lunch boxes to be distributed to each room i.

For security reasons, opening an external door for supply is allowed in only one room.

Once all lunch boxes enter a single room from the outside, they can be moved to adjacent rooms.

The supply officer wants the lunch boxes to be properly distributed to all rooms with the minimum travel distance.

In this case, the distance is the number of internal doors the lunch boxes pass through.

For example, suppose there are 5 rooms and the number of lunch boxes each room wants to receive is 4 7 8 6 4.

The total number of lunch boxes is 29.

Let's look at the case where 29 lunch boxes are delivered to room 1 using the external door.

1) The distance to move 4 lunch boxes to room 1 is 0.

2) The distance to move 7 lunch boxes to room 2 is 7*1 = 7 because they pass through 1 internal door.

3) The distance to move 8 lunch boxes to room 3 is 8*2 = 16 because they pass through 2 internal doors.

4) The distance to move 6 lunch boxes to room 4 is 6*2 = 12 because they pass through 2 internal doors.

5) The distance to move 4 lunch boxes to room 5 is 4*1 = 4 because they pass through 1 internal door.

6) Therefore, the sum of the distances in this case is 39.

Skipping the case of placing them in room 2, let's look at the case where 29 lunch boxes are delivered to room 3 using the external door.

1) The distance to move 4 lunch boxes to room 1 is 4*2 = 8 because they pass through 2 internal doors.

2) The distance to move 7 lunch boxes to room 2 is 7*1 = 7 because they pass through 1 internal door.

3) The distance to move 8 lunch boxes to room 3 is 0 because they pass through 0 internal doors.

4) The distance to move 6 lunch boxes to room 4 is 6*1 = 6 because they pass through 1 internal door.

5) The distance to move 4 lunch boxes to room 5 is 4*2 = 8 because they pass through 2 internal doors.

6) Therefore, the sum of the distances in this case is 29, which is the minimum value.

Write a program that calculates and outputs the minimum sum of distances that all lunch boxes must travel to be distributed to the N rooms according to the supply officer's plan.