题目描述

对于正整数 $k$ ，一个大小为 $k$ 的“金字塔数列”为一个长度为 $2k-1$ 的数列，里面的数字依次为 $1,2,3,...,k-1,k,k-1,...,3,2,1$ 。

现在给一个长度为 $n$ 的数列 $S$ ，你可以进行以下操作任意次，使得数列最后变为一个“金字塔数列”：

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

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

输入格式

第一行输入一个正整数 $n$ 。

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n$ 。

输出格式

输出最后生成的“金字塔数列”的最大的 $k$ 。

输入输出样例 #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\leq\ N\leq\ 2\times\ 10^5$
• $1\leq\ A_i\leq\ 10^9$