$\color{deeppink}link$

因为魔法序列的左右端点大小不定，我这里是左端点较小。但可以将询问和序列一起翻转，或用 $mx$ 减一下原序列，再跑一遍即可。

假设我们可以求出对于每个点作为左端点，向右最大可以的右端点，且限定右端点最大为 $i$，就可以求出答案。

那么对于询问 $(l_i,r_i)$，查询对于 $j\in[l_i,r_i]$，限定 $j$ 为左端点，右端点最大为 $r_i$ 的最大长度。

限定右端点可以从小到大限定。当前限定 $i$ 为最长的右端点，求出小于 $i$ 的点作为左端点的最长长度。离线查询即可。

考虑求出每个点作为左端点的最大右端点。搞一个不下降的单调栈，对于加入 $i$，有一下两种情况。

• $a_i\ge a_{k_{top}}$

$i$ 直接加入栈中，然后对于栈中元素位置大于 $to_i$（比 $a_i$ 大且位置比 $i$ 小的最后一个元素位置），把他们的的右端点置为 $i$，可以用一棵与栈中位置一一对应的线段树维护他们的魔法序列长度最大值。

• $a_i<a_{k_{top}}$

$k_{top}$ 的右端点不会再更新，把他踢到另一棵与原序列位置一一对应的线段树，然后要在第一棵树中把 $top$ 位置清空。一直踢到 $a_i\ge a_{k_{top}}$ 再加入 $i$。

求 $to_i$ 跑一次单调栈即可。

设当前处理到 $i$，对于询问 $(l,i)$，分别在两颗线段树中查询 $(l,i)$ 区间的最大值，注意第一棵线段树查询时用 lower_bound 求出节点在栈中的位置。

$code$

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+50;

struct ask
{
	int l,r,id;
	
	friend bool operator<(ask a,ask b)
	{
		return a.r<b.r;
	}
}p[N];

int n,a[N],mx,q,k[N],ans[N],top,to[N],A[N<<2],B[N<<2],la[N<<2],qu[N],tail;

void cc()
{
	memset(k,0,sizeof k);top=tail=0;
	memset(to,0,sizeof to);
	memset(A,0,sizeof A);
	memset(B,0,sizeof B);
	memset(la,0,sizeof la);
	memset(qu,0,sizeof qu);
}

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)

void down(int x,int l,int r)
{
	if(la[x])
	{
		la[ls]=la[rs]=la[x];
		A[ls]=la[x]-qu[l]+1;
		A[rs]=la[x]-qu[mid+1]+1;
		la[x]=0;
		return;
	}
}

void up(int x,int f)
{
	if(!f)A[x]=max(A[ls],A[rs]);
	else B[x]=max(B[ls],B[rs]);
}

void clear(int x,int l,int r,int d)
{
	if(l==r)
	{
		A[x]=0;
		return;
	}
	down(x,l,r);
	if(d<=mid)clear(ls,l,mid,d);
	else clear(rs,mid+1,r,d);
	up(x,0);
}

int find(int x,int l,int r,int L,int R)
{
	if(L<=l&&R>=r)return A[x];
	int ans=0;down(x,l,r);
	if(L<=mid)ans=max(ans,find(ls,l,mid,L,R));
	if(R>mid)ans=max(ans,find(rs,mid+1,r,L,R));
	return ans;
}

void add(int x,int l,int r,int d,int y)
{
	if(l==r)
	{
		B[x]=y;
		return;
	}
	if(d<=mid)add(ls,l,mid,d,y);
	else add(rs,mid+1,r,d,y);
	up(x,1);
}

void insert(int x,int l,int r,int L,int R,int d)
{
	if(L<=l&&R>=r)
	{
		A[x]=d-qu[l]+1;
		la[x]=d;
		return;
	}
	down(x,l,r);
	if(L<=mid)insert(ls,l,mid,L,R,d);
	if(R>mid)insert(rs,mid+1,r,L,R,d);
	up(x,0);
}

int get(int x,int l,int r,int L,int R)
{
	if(L<=l&&R>=r)return B[x];
	int ans=0;down(x,l,r);
	if(L<=mid)ans=max(ans,get(ls,l,mid,L,R));
	if(R>mid)ans=max(ans,get(rs,mid+1,r,L,R));
	return ans;
}

void sol()
{
	for(int i=n;i>=1;i--)
	{
		while(top&&a[i]>a[k[top]])to[k[top--]]=i;
		k[++top]=i;
	}
	for(int i=1,j=1;i<=n;i++)
	{
		while(tail&&a[qu[tail]]>a[i])
		{
			add(1,1,n,qu[tail],find(1,1,n,tail,tail));
			clear(1,1,n,tail);
			tail--;
		}
		qu[++tail]=i;
		int t=upper_bound(qu+1,qu+1+tail,to[i])-qu;t=max(t,1);
		insert(1,1,n,t,tail,i);
		while(j<=q&&p[j].r==i)
		{
			ans[p[j].id]=max(ans[p[j].id],get(1,1,n,p[j].l,p[j].r));
			int t=lower_bound(qu+1,qu+1+tail,p[j].l)-qu;
			ans[p[j].id]=max(ans[p[j].id],find(1,1,n,t,tail));
			j++;
		}
	}
}

main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],mx=max(a[i],mx);
	cin>>q;
	for(int i=1;i<=q;i++)cin>>p[i].l>>p[i].r,p[i].id=i;
	sort(p+1,p+1+q);
	sol();
	for(int i=1;i<=n;i++)a[i]=mx-a[i]+1;
	cc();sol();
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}