CF610B.Vika and Squares

Vika has n jars with paints of distinct colors. All the jars are numbered from 1 to n and the i-th jar contains a__i liters of paint of color i.

Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1 × 1. Squares are numbered 1, 2, 3 and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color x, then the next square will be painted in color x + 1. In case of x = n, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.

Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.

维卡有 $n$ 个装有不同颜色颜料的罐子。所有罐子编号为 $1$ 到 $n$，其中第 $i$ 个罐子含有 $a_i$ 升颜色为 $i$ 的颜料。

维卡还有一张无限长、宽度为 $1$ 的矩形纸条，由若干 $1 \times 1$ 的方格组成。方格从左至右依次编号为 $1, 2, 3, \dots$。维卡决定从第 $1$ 个方格开始，从左到右逐个涂色，起始颜色可任意选择。若当前方格涂的是颜色 $x$，则下一个方格将涂颜色 $x+1$；当 $x = n$ 时，下一个方格涂颜色 $1$。如果维卡当前需要使用的颜色已无剩余颜料，则她立即停止。

每个方格仅涂一种颜色，且恰好消耗 $1$ 升颜料。你的任务是：在恰当选取第一个方格所用颜色的前提下，计算最多能涂多少个方格。

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of jars with colors Vika has.

The second line of the input contains a sequence of integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109), where a__i is equal to the number of liters of paint in the i-th jar, i.e. the number of liters of color i that Vika has.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）——表示维卡拥有的颜料罐数量。

输入的第二行包含一个整数序列 $a_1,\,a_2,\,...,\,a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 个罐子中油漆的升数，即维卡所拥有的第 $i$ 种颜色的油漆升数。

The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.

输出仅应包含一行，且该行中只有一个整数——即维卡在遵循上述规则的情况下最多可以涂色的正方形数量。

In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In the second sample Vika can start to paint using any color.

In the third sample Vika should start painting using color number 5.

在第一个样例中，最优策略是使用颜色 4 开始涂色。此时方格将按如下颜色（从左到右）被涂色：4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5。

在第二个样例中，Vika 可以使用任意颜色开始涂色。

在第三个样例中，Vika 应该使用颜色 5 开始涂色。