题目描述

对于正整数 $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$

输出格式

输出最大的结果 $k$

5
2 2 3 1 1

2

5
1 2 3 4 5

3

1
1000000000

1

提示

数据范围

• $1\leq\ N\leq\ 2\times\ 10^5$
• $1\leq\ A_i\leq\ 10^9$
• 输入的都是整数

样例 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$ .