Yet Another Monster Fight
Contest: Educational Codeforces Round 158 (Rated for Div. 2)
Difficulty rating: 1700
Tags: binary search, dp, greedy, implementation, math

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6
2 1 5 6 4 3

Example output:
8

Example input:
5
4 4 4 4 4

Example output:
8

Editorial:
Let's start with a naive solution. Let $$$i$$$ be the index of the monster we started with. Let's make sure that we can kill all monsters, starting with monster $$$i$$$.
Suppose we have chosen spell power $$$x$$$. How to check if all monsters will be definitely killed? Let's iterate on each monster $$$j$$$ and calculate the minimum possible damage it can get:
• if $$$i = j$$$, then the $$$j$$$-th monster will receive exactly $$$x$$$ damage. So, $$$x$$$ should be at least $$$a_j$$$;
• if $$$i > j$$$, then the minimum amount of damage the $$$j$$$-th monster may receive happens when the spell first strikes all monsters to the right of monster $$$i$$$, and then goes to the left of monster $$$i$$$. It means that $$$n - j$$$ monsters will be struck before the $$$j$$$-th monster, so the $$$j$$$-th monster will receive $$$x - (n-j)$$$ damage. So, $$$x$$$ should be at least $$$a_j + (n-j)$$$ for every $$$j < i$$$;
• and if $$$i < j$$$, then the minimum amount of of damage the $$$j$$$-th monster may receive happens when the spell first strikes all monsters to the left of monster $$$i$$$, and then goes to the right of monster $$$i$$$. It means that $$$j-1$$$ monsters will be struck before the $$$j$$$-th monster, so the $$$j$$$-th monster will receive $$$x - (j-1)$$$ damage. So, $$$x$$$ should be at least $$$a_j + (j-1)$$$ for every $$$j > i$$$.
So, if we want to start with the $$$i$$$-th monster, the minimum spell power we need is $$$\max(\max\limits_{j=1}^{i-1} a_j + (n-j), a_i, \max\limits_{j=i+1}^{n} a_j + (j-1))$$$. This gives us a solution in $$$O(n^2)$$$, but it can be sped up to $$$O(n)$$$ using prefix and suffix maxima.