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 进行绘画。