サイズ \(s\) のピラミッド数列における第 \(s\) 項を頂点と呼ぶことにします。

最初に、元の数列 \(A\) の第 \(k\) 項 \(A_k\) が頂点となるようなサイズ \(s\) のピラミッド数列を、操作の繰り返しによって作ることができる条件について考えます。

まず、操作によって 項を増やすことはできないことから、左右に \(s-1\) 項ずつ存在する必要があります。 すなわち \(s\leq k\leq N-s+1\) です。
次に、操作によって取り除ける項はそれぞれの時点における先頭か末尾の項のみであることから、最終的に \((2s-1)\) 項のピラミッド数列を構成するのは 最初の \(A\) の\((k-s+1)\) 項目から \((k+s-1)\) 項目までとなります。 さらに、操作によって各項の値は非増加であることから、\(A_{i}\geq s-\lvert k-i\rvert\) \((k-s+1\leq i\leq k+s-1)\) である必要があることがわかります。

逆にこれらの条件をみたすとき、\(A\) から \((k-s)\) 項目以前と \((k+s)\) 項目以降を削除し、残った項を必要なだけ減少させることで条件をみたすピラミッド数列を作る事ができます。 よって、必要十分条件は

• \(s\leq k\leq N-s+1\) かつ \(A_{i}\geq s-\lvert k-i\rvert\) \((k-s+1\leq i\leq k+s-1)\)

です。ここで、\(1\leq i\leq k-s\), \(k+s\leq i\leq n\) であるような \(i\) についてはつねに \(s-\lvert k-i\rvert\leq 0<A_i\) が成り立つことに注意すると、

• \(s\leq k\leq N-s+1\) かつ \(A_{i}\geq s-\lvert k-i\rvert\) \((1\leq i\leq N)\)

と書き換えられます。さらに、\(A_0=A_{N+1}=0\) と置くと、\(s\leq k\Leftrightarrow A_0\geq s-\lvert k-0\rvert\), 同様に \(k\leq N-s+1 \Leftrightarrow A_{N+1}\geq s-\lvert k-(N+1)\rvert\) であるから 条件は

• \(A_{i}\geq s-\lvert k-i\rvert\) \((0\leq i\leq N+1)\)

と置き換えられます。

次に、\(A_k\) を頂点としたサイズ \(s\) のピラミッド数列を作ることができる \(s\) の最大値 \(s_M(k)\) について考えます。 これは先の条件が \(A_i+\lvert k-i\rvert\geq s\) \((0\leq i\leq N+1)\) と書き換えられることから、

\[ s_M(k)=\min_{0\leq i\leq N+1} (A_i+\lvert k-i\rvert) \]

によって求める事ができます。答えは \(1\leq k\leq N\) における \(s_M(k)\) の最大値であるので、 \(s_M(k)\) の値を \(k=1,2,\ldots,N\) に対して求めれば良いです。

しかし、これらの値を愚直に求めようとすると \(O(N^2)\) の時間がかかり、今回の制約の下では間に合いません。 そこで、さらにこの式を整理する事を考えます。
絶対値記号を外すと、

\[ \begin{aligned} s_M(k) &=\min\left(\min_{0\leq i\leq k} (A_i+k-i), \min_{k+1\leq i\leq N+1} (A_i+i-k) \right) \\ &= \min\left(\min_{0\leq i\leq k} (A_i-i) +k, \min_{k+1\leq i\leq N+1} (A_i+i) -k\right) \end{aligned} \]

となります。よって、\(i=1,2,\ldots,N\) について、\(m_1(k)=\displaystyle\min_{0\leq i\leq k} (A_i-i)\) と \(m_2(k)=\displaystyle\min_{k+1\leq i\leq N+1} (A_i+i)\) を求めれば良いです。

\(m_1(k)\)は \(m_1(1)=\min(A_0,A_1-1)\), \(m_1(k)=\min\left(m_1(k-1),A_k-k\right)\) \((2\leq k\leq N)\) の漸化式を用いて全ての値を \(O(N)\) で求める事ができます。
同様に、\(m_2(k)\) も \(m_2(N)=A_{N+1}+(N+1)\), \(m_2(k)=\min\left(m_2(k+1),A_{k+1}+k+1\right)\) \((1\leq k\leq N-1)\) によって求める事ができます。

あとは、\(\displaystyle\max_{1\leq k\leq N} \left\{\min(m_1(k)+k,m_2(k)-k)\right\}\) によって答えを求める事ができます。
この　手法によって答えを求めるときの時間計算量は \(O(N)\) であり、十分高速です。
よってこの問題を解く事ができました。

c++ による実装例

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n,ans=0;
	cin>>n;
	vector<int>a(n+2);
	vector<int>m1(n);
	vector<int>m2(n);
	for(int i=0;i<n;i++)cin>>a[i+1];

	m1[0]=min(a[0],a[1]-1);
	for(int i=1;i<n;i++)m1[i]=min(m1[i-1],a[i+1]-i-1);
	m2[n-1]=a[n+1]+n+1;
	for(int i=n-2;i>=0;i--)m2[i]=min(m2[i+1],a[i+2]+i+2);
	for(int i=0;i<n;i++)ans=max(ans,min(m1[i]+i+1,m2[i]-i-1));
	
	cout<<ans<<endl;
	return 0;
}