← 返回题目列表

Codeforces · 610/B

B. 维卡和广场

中文机器翻译题面 查看原题

Vika 有 n 个罐子,里面装有不同颜色的油漆。所有罐子都从 1 到 n 编号,第 i 个罐子包含 ai 升颜色为 i 的油漆。

Vika 还有一张宽度为 1 的无限长矩形纸,由大小为 1 × 1 的正方形组成。正方形的编号为 1、2、3 等。 Vika 决定从 1 号方块和一些任意颜色开始,从左到右逐个绘制方块。如果该方格被涂成颜色 x,则下一个方格将被涂成颜色 x + 1。如果 x = n,则下一个方格将被涂成颜色 1。如果现在没有更多的颜色维卡想要使用的颜色,那么她就会停止。

正方形总是只涂一种颜色,并且正好需要 1 升油漆。你的任务是计算如果维卡选择正确的颜色来绘制第一个方块,则可以绘制的最大方块数。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) - Vika 拥有的颜色罐子的数量。

输入的第二行包含一系列整数 a1, a2, ..., an (1 ≤ ai ≤ 109),其中 ai 等于第 i 个罐子中油漆的升数,即 Vika 拥有的颜色 i 的升数。

输出

输出的唯一一行应包含一个整数 - 如果 Vika 遵循上述规则,她可以绘制的最大方块数。

示例

输入 #1

5
2 4 2 3 3

输出 #1

12

输入 #2

3
5 5 5

输出 #2

15

输入 #3

6
10 10 10 1 10 10

输出 #3

11

注意

在第一个示例中,最佳策略是开始使用颜色 4 进行绘制。然后将使用以下颜色(从左到右)绘制方块:4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5。

在第二个示例中,Vika 可以开始使用任何颜色进行绘画。

在第三个示例中,Vika 应开始使用颜色编号 5 进行绘画。