408546: GYM103185 C Crisis at the Wedding

Memory Limit:1024 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Crisis at the Weddingtime limit per test0.25 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

A famous football player just got married and is holding a party for his wedding guests. The guests are seated at tables around a circular pond in the garden of the player's villa. Each table accommodates exactly the same number of guests, and consecutive tables around the pond are at a unit distance.

At the moment of the traditional Best Man toast a crisis erupted: although the total number of champagne glasses in the guests' tables is exactly the number of guests, the glasses could have been distributed unevenly over the tables, with some tables having more glasses than guests and some other tables having fewer glasses than guests.

A single waiter is available to fix the glasses distribution, collecting surplus glasses from tables and delivering them to tables needing glasses. The cost of each glass fix is the distance the waiter carries the glass until he delivers it to a table. The total cost for the operation is the sum of the costs for all glasses. The waiter can start at any table, but the player is superstitious and will only allow the waiter to walk in a strict clockwise or counterclockwise direction when fixing the glasses distribution. That is, once the waiter starts in one direction (clockwise or counterclockwise) he cannot change the direction.

Earn an autographed jersey from the football player by helping him to calculate the smallest possible total cost for fixing the glasses distribution.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$) indicating the number of tables around the circular pond. The second line contains $$$N$$$ integers $$${G_1}, {G_2}, \ldots, {G_N}$$$ ($$$0 \leq G_i \leq 1000$$$ for $$${i} = {1}, {2}, \ldots, {N}$$$), representing the number of glasses in the different tables. These numbers are given in clockwise order. It is guaranteed that $$$N$$$ divides $$$\sum_{i=1}^N G_i$$$.

Output

Output a single line with an integer indicating the smallest possible total cost for fixing the glasses distribution.

ExamplesInput
4
14 10 6 10
Output
8
Input
6
24 122 0 37 49 242
Output
454
Input
6
0 0 0 0 60 0
Output
150
Input
1
0
Output
0

加入题单

上一题 下一题 算法标签: