该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

对于一个正整数 $k$，一个长度为 $2k-1$ 的"回文数列"定义为其元素依次为$1、2、3\ldots、k-1、k、k-1 \ldots、3、2、1$。现在，给定一个长度为$n$的数列$s$，你可以进行以下任意次操作，最终使得数列变为一个回文数列：

• 选择数列中的一个元素 $i (1 \leq i \leq n))$，将 $s_i$减少 1。
• 删除整个数列的第一个或最后一个元素。

你需要解决的问题是，最大的$k$是多少，即能形成的最大的回文数列的大小是多少。

输入格式

第一行，一个正整数$n$，表示数列的长度。

第二行，$n$个空格隔开的正整数，表示数列中每一个数。

输出格式

输出一个整数，表示能通过上述操作得到的最大回文数列的大小$k$。

样例

样例输入1

5
2 2 3 1 1

样例输出1

2

样例输入2

5
1 2 3 4 5

样例输出2

3

样例输入3

1
1000000000

样例输出3

1

数据范围

$30\%$的数据满足，$1 \leq N \le 10^3$，$1 \leq s_i \leq 10^9$

$100\%$的数据满足，$1 \leq N \leq 2 \times 10^5$，$1 \leq s_i \leq 10^9$

样例解释

从$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$个元素，将其减少$1$，数列变为$A=(1, 2, 1)$。
• $A=(1, 2, 1)$这个回文数列中的最大值为$2$。不可能通过任何操作得到最大值为$3$或更大的回文数列，因此输出2。