金字塔

题目描述

对于正整数 $k$，大小为 $k$ 的「金字塔序列」是长度为 $2k-1$ 的序列，其中各项的值依次为 $1,2,\ldots,k-1,k,k-1,\ldots,2,1$。

给定长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$。

请通过对 $A$ 重复进行以下操作（可以是零次），求出能得到的金字塔序列的最大大小。

• 选择序列中的一项，将其值减 $1$。
• 删除第一个或最后一个元素。

可以证明，在题目给定的约束下，至少可以通过重复操作得到一个金字塔序列。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出对序列 $A$ 重复进行题目所述操作后能得到的金字塔序列的最大大小。

样例

5
2 2 3 1 1

2

从 $A=(2,2,3,1,1)$ 出发，可以如下得到大小为 $2$ 的金字塔序列：

选择第 3 项并减 $1$，序列变为 $A=(2,2,2,1,1)$。

删除第一个元素，序列变为 $A=(2,2,1,1)$。

删除最后一个元素，序列变为 $A=(2,2,1)$。

选择第一个元素并减 $1$，序列变为 $A=(1,2,1)$。

$(1,2,1)$ 是大小为 $2$ 的金字塔序列。

另一方面，无法通过操作得到大小为 $3$ 或更大的金字塔序列，因此应输出 $2$。

5
1 2 3 4 5

3

1
1000000000

1

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 所有输入均为整数。