310863: CF1901D. Yet Another Monster Fight

D. Yet Another Monster Fighttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExamplesInput

6
2 1 5 6 4 3

Output

8

Input

5
4 4 4 4 4

Output

8

Input

2
1 1000000000

Output

1000000000

题目大意：
Vasya是一位战斗法师，他在战斗中使用连锁闪电法术对抗排列成一排的n只怪物。每只怪物i的血量为a_i。Vasya选择一个怪物i作为连锁闪电的起始目标，并设定法术的初始威力x。法术会恰好攻击n次，每次攻击一个怪物。第一次攻击的目标是怪物i，之后每次攻击会选择一个未被攻击过的、与已被攻击的怪物相邻的随机怪物。每个怪物被攻击一次，第一次攻击造成x点伤害，之后每次攻击伤害减少1。Vasya想要用一个连锁闪电法术杀死所有怪物，即使是在最坏的情况下。他希望找到最小的初始威力x，使得所有怪物都被杀死。Vasya会选择最佳的起始目标和法术威力，其他情况随机。求最小的初始威力x。

输入数据格式：
第一行包含一个整数n（1≤n≤3×10^5），表示怪物的数量。
第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），分别表示每只怪物的血量。

输出数据格式：
输出一个整数，表示最小的法术初始威力x，使得Vasya能够杀死所有怪物。题目大意： Vasya是一位战斗法师，他在战斗中使用连锁闪电法术对抗排列成一排的n只怪物。每只怪物i的血量为a_i。Vasya选择一个怪物i作为连锁闪电的起始目标，并设定法术的初始威力x。法术会恰好攻击n次，每次攻击一个怪物。第一次攻击的目标是怪物i，之后每次攻击会选择一个未被攻击过的、与已被攻击的怪物相邻的随机怪物。每个怪物被攻击一次，第一次攻击造成x点伤害，之后每次攻击伤害减少1。Vasya想要用一个连锁闪电法术杀死所有怪物，即使是在最坏的情况下。他希望找到最小的初始威力x，使得所有怪物都被杀死。Vasya会选择最佳的起始目标和法术威力，其他情况随机。求最小的初始威力x。 输入数据格式： 第一行包含一个整数n（1≤n≤3×10^5），表示怪物的数量。 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），分别表示每只怪物的血量。 输出数据格式： 输出一个整数，表示最小的法术初始威力x，使得Vasya能够杀死所有怪物。