该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

隔壁的空位（shelf）

题目描述

档案室要更换一整排规格相同的柜格。现在有 $n$ 格，从左到右编号为 $1,2,\ldots,n$，第 $i$ 格原来存放 $a_i$ 份档案。每份档案占据一个存放位置。

Y 同学可以让一份档案留在原格，也可以把它搬到原格右边相邻的一格。每份档案至多搬一次：从别的格子搬进来的档案不能再次向右转交；原本在最后一格的档案只能留在原格。不能丢弃档案，也不能将档案搬到左边或隔着一格的地方。

新柜格的容量统一为非负整数 $C$。求能容纳所有档案的最小 $C$，即经过合法搬动后，每一格的档案数量都不超过 $C$。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示新柜格的最小容量。

样例

样例输入 #1

3
8 0 0

样例输出 #1

4

样例输入 #2

3
0 0 8

样例输出 #2

8

样例输入 #3

4
0 0 0 0

样例输出 #3

0

数据范围与约定

对于所有数据，保证 $1\le n\le2\times10^5$，$0\le a_i\le10^9$。

每个测试点 $5$ 分，分档如下：

特殊性质 A：所有 $a_i$ 相等。

特殊性质 B：所有 $a_i\le1$。