CF1901D.Yet Another Monster Fight

Vasya is a sorcerer that fights monsters. Again. There are $n$ monsters standing in a row, the amount of health points of the $i$-th monster is $a_i$.

Vasya is a very powerful sorcerer who knows many overpowered spells. In this fight, he decided to use a chain lightning spell to defeat all the monsters. Let's see how this spell works.

Firstly, Vasya chooses an index $i$ of some monster ($1 \le i \le n$) and the initial power of the spell $x$. Then the spell hits monsters exactly $n$ times, one hit per monster. The first target of the spell is always the monster $i$. For every target except for the first one, the chain lightning will choose a random monster who was not hit by the spell and is adjacent to one of the monsters that already was hit. So, each monster will be hit exactly once. The first monster hit by the spell receives $x$ damage, the second monster receives $(x-1)$ damage, the third receives $(x-2)$ damage, and so on.

Vasya wants to show how powerful he is, so he wants to kill all the monsters with a single chain lightning spell. The monster is considered dead if the damage he received is not less than the amount of its health points. On the other hand, Vasya wants to show he doesn't care that much, so he wants to choose the minimum initial power of the spell $x$ such that it kills all monsters, no matter which monster (among those who can get hit) gets hit on each step.

Of course, Vasya is a sorcerer, but the amount of calculations required to determine the optimal spell setup is way above his possibilities, so you have to help him find the minimum spell power required to kill all the monsters.

Note that Vasya chooses the initial target and the power of the spell, other things should be considered random and Vasya wants to kill all the monsters even in the worst possible scenario.

瓦西娅是一名与怪物作战的巫师，这已经不是第一次了。现在有 $n$ 只怪物排成一列，第 $i$ 只怪物的生命值为 $a_i$。

瓦西娅是一位极其强大的巫师，掌握着许多超强力的法术。在本次战斗中，他决定使用“连锁闪电”法术一次性消灭所有怪物。下面我们来了解该法术的具体机制：

首先，瓦西娅选择某个怪物的下标 $i$（$1 \le i \le n$）作为初始目标，并设定法术的初始威力 $x$。随后，该法术将恰好命中 $n$ 次，每次命中一只怪物。第一次命中的目标必定是第 $i$ 只怪物；对于其余每次命中（即除第一次外的所有命中），连锁闪电会随机选择一只尚未被命中的怪物，且该怪物必须与至少一只已被命中的怪物相邻。因此，每只怪物恰好被命中一次。第一只被命中的怪物受到 $x$ 点伤害，第二只受到 $(x-1)$ 点伤害，第三只受到 $(x-2)$ 点伤害，依此类推。

瓦西娅想借此展示自己有多么强大，因此他希望仅用一次连锁闪电法术就消灭全部怪物。当一只怪物所受伤害不小于其生命值时，该怪物即被视为死亡。另一方面，瓦西娅还想表现出自己对此并不十分在意，因此他希望选择最小的初始法术威力 $x$，使得无论后续每次命中的是哪个合法可选的怪物（即满足前述“未被命中且与已命中怪物相邻”的条件），所有怪物都能被消灭。

当然，瓦西娅虽是巫师，但要手动计算出最优法术配置所需的大量运算已远超他的能力范围，因此你需要帮他找出能消灭所有怪物所需的最小法术威力。

注意：瓦西娅自主选择初始目标和法术威力 $x$；其余过程视为随机，而瓦西娅要求：即使在最坏情况下（即每次随机选择都对瓦西娅最不利），所有怪物也必须被消灭。

The first line of the input contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of monsters.

The second line of the input contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the amount of health points of the $i$-th monster.

输入的第一行包含一个整数 $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$ 个怪物的生命值。

Print one integer — the minimum spell power required to kill all the monsters if Vasya chooses the first target optimally, and the order of spell hits can be any possible within the given rules.

输出一个整数——如果瓦西娅最优地选择第一个目标，且法术攻击的顺序可以是满足给定规则的任意可能顺序，则杀死所有怪物所需的最小法术威力。