题目描述

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

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

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

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

输入格式

第一行一个整数 $n$；

第二行 $n$ 个整数，构成了数列 $S$。

输出格式

输出一个整数，表示答案。

5
2 2 3 1 1

2

提示

对于 $30\%$ 的数据，$1≤n≤100$；

对于 $50\%$ 的数据，$1≤n≤10000$；

对于 $100\%$ 的数据，$1≤n≤200000$，$1≤S_i≤10000000$。