又一次怪物战斗

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $n$ 个怪物排成一行，第 $i$ 个怪物的生命值为 $a_i$。你要施展一次魔法：先选择一个位置作为第一个被直接攻击的怪物，再选择魔法威力 $x$。

第 $s$ 个受到攻击的怪物会承受 $x-s+1$ 点伤害。第一次攻击后，每一步可以任意选择一个与已经攻击过的区域相邻、且尚未攻击的怪物。因此，已经攻击的位置始终构成一个连续区间，下一步可以攻击该区间左边或右边紧邻的怪物（若存在）。

你可以选择第一次攻击的位置。求最小的 $x$，使得无论之后采用哪一种合法攻击顺序，每个怪物受到的伤害都不少于它的生命值。

输入格式

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

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

输出格式

输出所需的最小魔法威力 $x$。

样例输入 1

6
2 1 5 6 4 3

样例输出 1

8

样例输入 2

5
4 4 4 4 4

样例输出 2

8

样例输入 3

2
1 1000000000

样例输出 3

1000000000

数据范围

$1\le n\le3\times10^5$，$1\le a_i\le10^9$。