Monty Hall's Circular Door Game

A new game inspired by Monty Hall is played using n doors arranged in a circle. The player starts standing in front of door 1 and in each round he performs the following steps:

1. Select an integer i (where 1 ≤ i ≤ n-1).
2. Pay a cost of C_i to move i steps to the right (the doors form a circle).
3. Open the door at the position where he lands.

It is guaranteed that the costs satisfy the condition $$C_i \ge C_{i+1} \quad\text{for } 1 \le i < n.$$

The objective is to open all n doors at the minimum total cost. Note that a door is only opened when the player lands on it in a move; the starting door is not automatically opened. An optimal strategy is to repeatedly choose the move with the smallest cost. Since the cost array is non-increasing, the move of n-1 steps (which is always co-prime with n) is optimal, because repeating this move will eventually open all the doors. Therefore, the minimum total cost is $$n\times C_{n-1}.$$

inputFormat

The input consists of two lines:

• The first line contains an integer n (2 ≤ n ≤ 10⁵), representing the number of doors arranged in a circle.
• The second line contains n-1 space-separated integers, C₁, C₂, ..., C_n-1, where C_i is the cost to move i steps. It is guaranteed that C_i ≥ C_i+1 for 1 ≤ i < n.

outputFormat

Output a single integer, which is the minimum total cost required to open all the doors.

sample

2
100

200