[ABC336D] Pyramid

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

[problemUrl]: https://atcoder.jp/contests/abc336/tasks/abc336_d 正の整数 $ k $ について、サイズ $ k $ の **ピラミッド数列** とは、長さ $ (2k-1) $ の数列であって各項の値が順に $ 1,2,\ldots,k-1,k,k-1,\ldots,2,1 $ であるようなものをさします。 長さ $ N $ の数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ A $ に対して、次の操作のうち一方を選んで行うことを繰り返して ($ 0 $ 回でも良い) 得ることのできるピラミッド数列のサイズの最大値を求めてください。 - 数列の項を $ 1 $ つ選び、その項の値を $ 1 $ 減少させる。 - 先頭または末尾の項を削除する。 なお、問題の制約のもとで、操作を繰り返すことで必ず $ 1 $ 種類以上のピラミッド数列を得ることができることが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

数列 $ A $ に問題文の操作を繰り返して得ることのできるピラミッド数列のサイズの最大値を出力せよ。

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 $ - 入力はすべて整数 ### Sample Explanation 1 $ A=(2,2,3,1,1) $ から始めて、 次のようにして数列 $ A $ からサイズ $ 2 $ のピラミッド数列を作る事ができます。 - 第 $ 3 $ 項を選び、$ 1 $ 減少させる。数列は $ A=(2,2,2,1,1) $ となる。 - 先頭を削除する。数列は $ A=(2,2,1,1) $ となる。 - 末尾を削除する。数列は $ A=(2,2,1) $ となる。 - 第 $ 1 $ 項を選び、$ 1 $ 減少させる。数列は $ A=(1,2,1) $ となる。 $ (1,2,1) $ はサイズ $ 2 $ のピラミッド数列です。 一方、どのように操作を行ってもサイズ $ 3 $ 以上のピラミッド数列を作ることはできないため $ 2 $ を出力します。