Let us call the \(s\)-th term of a pyramid sequence of size \(s\) its top.

Initially, we consider the condition in which repeatedly applying the operation makes it a size-\(s\) pyramid sequence with the opt being the \(k\)-th term \(A_k\) of the original sequence \(A\).

Firstly, the operation does not insert a term, so there must be \((s-1)\) terms on its left and right. Formally, \(s\leq k\leq N-s+1\).
Next, an operation can remove only the first or last term at that point, so the resulting pyramid sequence with \((2s-1)\) terms consists of the \((k-s+1)\)-th through \((k+s-1)\)-th term of the initial \(A\). Moreover, the operation does not increase the terms, so \(A_{i}\geq s-\lvert k-i\rvert\) must hold.

Conversely, if these conditions are satisfied, then one can obtain a pyramid sequence by removing the \((k-s)\)-th and preceding terms, and \((k+s)\)-th and succeeding, and decreasing the other terms as much as required. Thus, the necessary and sufficient condition is

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

Here, any \(i\) with \(1\leq i\leq k-s\) or \(k+s\leq i\leq n\) satisfies \(s-\lvert k-i\rvert\leq 0<A_i\), so it is equivalent to

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

Furthermore, if we let \(A_0=A_{N+1}=0\), then \(s\leq k\Leftrightarrow A_0\geq s-\lvert k-0\rvert\), and similarly \(k\leq N-s+1 \Leftrightarrow A_{N+1}\geq s-\lvert k-(N+1)\rvert\), so the condition is rewritten to

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

Then, we consider \(s_M(k)\), the maximum \(s\) such that a size-\(s\) pyramid with the top being \(A_k\) can be constructed. Since the condition above is equivalent to \(A_i+\lvert k-i\rvert\geq s\) \((0\leq i\leq N+1)\), it can be found as

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

The answer is the maximum \(s_M(k)\) over \(1\leq k\leq N\), so it is sufficient to evaluate \(s_M(k)\) for all \(k=1,2,\ldots,N\).

However, trying to find this value naively costs a total of \(O(N^2)\) time, which is too costly for the constraints this time. So we try to further deform the expression.
Removing the absolute value sign, we have

\[ \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} \]

Thus, for \(i=1,2,\ldots,N\), it is sufficient to find \(m_1(k)=\displaystyle\min_{0\leq i\leq k} (A_i-i)\) and \(m_2(k)=\displaystyle\min_{k+1\leq i\leq N+1} (A_i+i)\).

\(m_1(k)\) can be found in a total of \(O(N)\) time using the following recurrence relation: \(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)\).
Likewise, \(m_2(k)\) can also be evaluated by \(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)\).

All that left is to find the answer as \(\displaystyle\max_{1\leq k\leq N} \left\{\min(m_1(k)+k,m_2(k)-k)\right\}\).
The time complexity using this method is \(O(N)\), which is fast enough.
Therefore, the problem has been solved.

Sample code in 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;
}