G. Monty Hall
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Once upon a time, there was a game show host named Monty Hall. He loved nothing more than to watch his contestants squirm as they tried to win fabulous prizes. One day he decided to spice things up by introducing a new game.

Eager to win a big prize and live a stress free life, Gigel decided to bite the bullet and take Monty Hall on his challenge.

The challenge is simple, Monty would show the contestant $$$N (1 \leq N \leq 10^5)$$$ doors, the contestant is initially positioned in front of the first door, however he can only unlock a door once he has moved onto that particular door. Gigel now has a selection of $$$N$$$ operations of the following types: he can select a number $$$i (1 \leq i \leq N)$$$ and must move $$$i$$$ doors to the right. The cost of this operation is equal to $$$C_i(1 \leq C_i \leq 10^5)$$$. It's important to note that these doors are arranged in a circle, hence the door to the right of the $$$N^{th}$$$ door is door number one.

Moreover, because Monty does not want to make it easy for Gigel to go from one door to the next one, the costs that he set for these operations are non-increasing. Formally, $$$C_i\geq C_{i+1}$$$ for all $$$1\leq i \leq N-1$$$.

In order to win Gigel has to open every door while keeping the overall cost as low as possible.

Gigel didn't exactly ace his Math classes in his younger days. Let's just say he was more interested in playing hooky and catching up on his beauty sleep. Now, he's hoping to make up for lost time and is seeking your help to crack this door-opening puzzle. And don't worry, he's willing to share the spoils of victory with you. After all, what are friends for, right?

Input

The first line of input contains one integer, $$$N (1 \leq N \leq 10^5)$$$, the number of doors.

The second line of input contains $$$N$$$ integers, where the $$$i^{th}$$$ element represents the cost of operation $$$i$$$ with $$$1 \leq C_i \leq 10^5$$$. It is guaranteed that $$$C_i\geq C_{i+1}$$$ for all $$$1\leq i \leq N-1$$$.

Output

The output file should contain one integer representing the minimum cost to open all $$$N$$$ doors.

Example
Input
5
4 3 3 3 3
Output
15
Note

Starting from door one, you take a 2-step move to the right at a cost of 3 and open door 3. Next, you make another 2-step move to the right with a cost of 3, opening door 5. Subsequently, you take a 4-step move to the right with a cost of 3, opening door 4. Afterward, you move 3 steps to the right at a cost of 3, opening door 2. Finally, you move 4 steps to the right with a cost of 3, opening door 1. In total, the cost incurred is 3+3+3+3+3, which amounts to 15.