题目描述

William and his friends are on a camping trip and have gathered some wooden blocks. Before nightfall, they stack these wooden blocks into $N$ stacks from left to right. The $i$-th stack has $W_i$ wooden blocks stacked on top of each other.

Each wooden block takes exactly one minute to burn. Once a wooden block is completely burnt, the fire will spread to all wooden blocks adjacent to it (the blocks immediately to its left, right, above, and below) and start burning them.

William starts burning from the outermost blocks, i.e. the blocks whose either left, right, or above side contains no blocks. Determine the total number of minutes required for all of the wood blocks to be completely burnt.

输入格式

The first line contains an integer $N$ ($1 \le N \le 200\;000$).

The second line contains $N$ integers representing $W_i$ ($0 \le W_i \le 10^9$), the number of wooden blocks in each stack.

输出格式

A single line representing the number of minutes required for all blocks to be completely burnt.

5
2 3 4 2 3

3

13
2 5 6 6 4 3 4 3 1 2 4 8 4

4

3
1 0 2

1

1
0

0

提示

$\textit{Explanation of Sample 1:}$ The following illustrates the burning process.

:::align{center} :::