#GYM104720F. Chef Circle

Chef Circle

Description

As the chefs await the dishes to be finalized, they sit around a circular table. Let the chefs be $1, 2, \dots, n$, where $n$ ($1\leq n \leq 10^5$) represents the number of chefs — yes, being the international chef's day, we may have many chefs join us, and we say chef $i$ has tastebud index $C_i$ ($1 \leq C_i \leq 10^9$).

As the judging process begins, a waiter stands behind chef $k$ ($1\leq k \leq n$), and pass the dish to the chef, so that the chef may taste and judge the dish. Once that is completed, the waiter moves on to chef $k+1$; if $k=n$, then the waiter would move on to chef $1$. This process (of passing the dish, recording the chef's rating, and moving to the next chef) continues until every chef has had the chance to taste the dish, and each time, the chef's tastebud index would be added up.

The chefs are impatient and that impacts their tastebuds' sensitivity: if they are the $i$th chef to be given the dish, their tastebud index is multiplied by $i$. As the contest organizer, you desire the maximum sum of tastebud index so that the judged dish is under the most rigorous scrutiny from the chefs' tastebuds: so it is your job to determine the optimal total tastebud index obtainable from the $n$ chefs given their tastebud indexes over all the possible chefs that the waiter may start with.

The first line consists of one number, $n$, representing the number of chefs.

The second line consists of $n$ numbers, representing the tastebud index $C_1, C_2, \dots, C_n$ of chefs $1 \dots n$.

Only one number representing the maximum sum of the total tastebud index with the impatience multiplier as described earlier.

Input

The first line consists of one number, $n$, representing the number of chefs.

The second line consists of $n$ numbers, representing the tastebud index $C_1, C_2, \dots, C_n$ of chefs $1 \dots n$.

Output

Only one number representing the maximum sum of the total tastebud index with the impatience multiplier as described earlier.

6
2 3 5 1 9 10
3
1 4 2
132
16

Note

There are a total of 6 possible chefs that the waiter may start with, and we will calculate the total tastebud index with impatience multiplier for each possibility:

Beginning from chef 1: $1\times 2 + 2\times 3 + 3\times 5 +4\times 1 + 5\times 9 + 6\times 10 = 132$

Beginning from chef 2: $6\times 2 + 1\times 3 + 2\times 5 +3\times 1 + 4\times 9 + 5\times 10 = 114$

Beginning from chef 3: $5\times 2 + 6\times 3 + 1\times 5 +2\times 1 + 3\times 9 + 4\times 10 = 102$

Beginning from chef 4: $4\times 2 + 5\times 3 + 6\times 5 +1\times 1 + 2\times 9 + 3\times 10 = 102$

Beginning from chef 5: $3\times 2 + 4\times 3 + 5\times 5 +6\times 1 + 1\times 9 + 2\times 10 = 78$

Beginning from chef 6: $2\times 2 + 3\times 3 + 4\times 5 +5\times 1 + 6\times 9 + 1\times 10 = 102$

Of which, beginning from chef 1 yields the best total tastebud index, so we return that index, which is 132.