题目描述

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

第二行$N$个整数$A_i$。

输出格式

一个整数ans表示答案。

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