Vasya 是一位与怪物战斗的魔法师。再次。有$$$n$$$个怪物排成一排,第$$$i$$$个怪物的生命值为$$$a_i$$$。
瓦西亚是一位非常强大的巫师,他知道许多强大的法术。在这场战斗中,他决定使用连锁闪电法术来击败所有怪物。让我们看看这个咒语是如何运作的。
首先,Vasya 选择某个怪物的索引 $$$i$$$ ($$$1 \le i \le n$$$) 和法术的初始威力 $$$x$$$。然后该法术会准确命中怪物 $$$n$$$ 次,每个怪物命中一次。该法术的第一个目标始终是怪物$$$i$$$。对于除第一个目标之外的每个目标,连锁闪电都会随机选择一个未被该法术击中且与已被击中的怪物相邻的怪物。因此,每个怪物只会被击中一次。该法术击中的第一个怪物会受到 $$$x$$$ 伤害,第二个怪物会受到 $$$(x-1)$$$ 伤害,第三个怪物会受到 $$$(x-2)$$$ 伤害,依此类推。
瓦夏想要展示自己的力量有多么强大,所以他想用一个闪电链法术杀死所有的怪物。如果怪物受到的伤害不低于其生命值,则视为死亡。另一方面,瓦斯亚想表明他并不在乎那么多,所以他想选择法术的最小初始威力$$$x$$$,这样它就能杀死所有怪物,无论每一步击中哪个怪物(在那些可能被击中的怪物中)。
当然,瓦斯亚是一名魔法师,但确定最佳法术设置所需的计算量远远超出了他的可能性,所以你必须帮助他找到杀死所有怪物所需的最低法术强度。
请注意,Vasya 选择初始目标和法术强度,其他事情应该被认为是随机的,即使在最坏的情况下,Vasya 也想杀死所有怪物。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 怪物的数量。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个怪物的生命值。
输出
打印一个整数——如果 Vasya 最佳选择第一个目标,则杀死所有怪物所需的最小法术强度,并且法术命中的顺序可以是给定规则内的任何可能的顺序。
示例
输入 #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