题目描述

对于正整数 $k$，一个大小为 $k$ 的“金字塔数列”为一个长度为 $2k-1$ 的数列，里面的数字依次为 $1,2,3,\dots k-1,k,k-1,\dots 3,2,1$。
现在给一个长度为 $n$ 的数列 $S$，你可以进行以下操作任意次，使得数列最后变为一个“金字塔数列”：

• 选择一个数 $i(1 \le i \le n)$，把 $S_i$ 减少 $1$。
• 删除整个数列的第一个或最后一个数字。

问最后生成的“金字塔数列”的最大的 $k$ 是多少。

输入格式

第一行输入 $N$

第二行输入 $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

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

样例 #1

样例输入 #1

5
2 2 3 1 1

样例输出 #1

2

样例 #2

样例输入 #2

5
1 2 3 4 5

样例输出 #2

3

样例 #3

样例输入 #3

1
1000000000

样例输出 #3

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\leq\ N\leq\ 2\times\ 10^5$
• $1\leq\ A_i\leq\ 10^9$
• 所有输入均为整数