题目背景

Special for beginners, ^_^

题目描述

有 n 个盒子，编号 1 到 n，每个盒子里有一些球。

第 i 个盒子最初有 ai 个球。

接下来进行 n 次操作，第 i 次操作如下：

取出第 i 个盒子里的所有球，记为 x。

将第 i 个盒子清空。

从第 i+1 个盒子开始，按顺序每个盒子放入 1 个球，直到放完 x 个球。

盒子是循环的：

n 的下一个是 1

1 的前一个是 n

所有操作结束后，输出 球最多的盒子中的球数。

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数：

a1 a2 ... an

数据范围：

1 ≤ n ≤ 2e5 0 ≤ ai ≤ 1e9

输出格式

输出一个整数，表示最后球最多的盒子中的球数。

样例

5
1 2 3 4 5

6

样例解释

初始：

1 2 3 4 5

操作1：

取出1个球，从2开始放

0 3 3 4 5

操作2：

取出3个球，从3开始放

0 0 4 5 6

操作3：

取出4个球，从4开始放

1 1 0 6 7

操作4：

取出6个球，从5开始放

3 2 1 0 9

操作5：

取出9个球，从1开始放

5 4 3 2 0

最大值：

5