题目描述

对于正整数$k$，大小为$k$的"金字塔序列"是一个长度为$(2k-1)$的序列，其中序列的项依次为$1,2,...,k-1,k,k-1,...,2,1$。

给定一个长度为$N$的序列$A=(A_1,A_2,...,A_N)$。
找出通过重复选择并执行以下操作（可能零次）对$A$进行操作后可以获得的最大金字塔序列的大小。

• 选择序列中的一项并将其值减少1。
• 移除第一项或最后一项。

可以证明，问题的约束条件保证至少可以通过重复操作获得一个金字塔序列。

输入格式

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

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

打印通过对序列$A$重复执行上述操作可以获得的最大金字塔序列的大小。

样例

5
2 2 3 1 1

2

5
1 2 3 4 5

3

1
1000000000

1

样例1解释

从A=(2,2,3,1,1)开始，你可以创建一个大小为2的金字塔序列，如下所示：

• 选择第三项并将其减少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。

数据范围

$1 ≤ N ≤ 2 × 10^5，1 ≤ A_i ≤ 10^9$。所有输入值都是整数。

来源

• AtCoder ABC336D