Problem Description

Monty Hall is a game show host. One day, he decided to introduce a new game.

There are a total of $n$ doors arranged in a circle. The player is initially standing in front of door $1$. In each round, the player performs the following operations: choose an integer $i$, pay a cost of $C_i$ to move $i$ steps to the right, and then the player opens the door at their current position. In particular, it is guaranteed that $C_i\geq C_{i+1}(1\leq i<n)$.

The player wants to know the minimum total cost needed to open all doors.

Input Format

The first line contains an integer $N(1\leq N\leq 10^5)$.

The next line contains $N$ integers $C_i(1\leq C_i\leq 10^5)$.

Output Format

One integer, representing the answer.

5
4 3 3 3 3

15

Hint

Translated by ChatGPT 5