Chain Lightning - Titan Online Assessment

Problem Preview

"Level : Codeforces Div-2 D Coder Coder is fighting a group of `n` monsters arranged in a straight line. The health of the `i`-th monster is `a_i`. Coder Coder has a special attack that can defeat the monsters one by one. Before starting, he chooses one monster as the starting point. The attack works as follows: * On the first move, Coder Coder attacks the chosen monster. * After that, he can attack any monster that is adjacent to at least one monster that has already been attacked. * Each monster is attacked exactly once. If a monster is attacked on the `k`-th move, Coder Coder needs to have an attack power of at least: `a_i + k - 1` for that monster to be defeated. Coder Coder wants to choose the starting monster and the attack power optimally so that **all monsters can be defeated**. Find the minimum attack power required. ## Input The first line contains a single integer `n` — the number of monsters. The second line contains `n` integers: `a_1, a_2, ..., a_n` where `a_i` is the health of the `i`-th monster. ## Constraints * `1 ≤ n ≤ 3 · 10^5` * `1 ≤ a_i ≤ 10^9` ## Output Print one integer — the minimum initial attack power Coder Coder needs to defeat all the monsters. ## Examples ### Example 1 **Input** ```text 6 2 1 5 6 4 3 ``` **Output** ```text 8 ``` ### Example 2 **Input** ```text 5 4 4 4 4 4 ``` **Output** ```text 8 ``` ### Example 3 **Input** ```text 2 1 1000000000 ``` **Output** ```text 1000000000 ```"