/* 线段树开到*4 *4 *4 *4 ！ 维护 4个值 区间最大值 区间最小值 从左往右跑最大收益 从右往左跑最大收益 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 200010 #define inf 0x7fffffff using namespace std; int n,m,num,a[maxn]; struct node { int lc,rc; int l,r; int smin,smax; int ansl,ansr; }t[maxn*4]; int init() { int x=0;char s;bool f=0;s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9') { x=x*10+s-'0'; s=getchar(); } return x; } void update(int k) { t[k].smin=min(t[t[k].lc].smin,t[t[k].rc].smin); t[k].smax=max(t[t[k].lc].smax,t[t[k].rc].smax); t[k].ansl=max(t[t[k].lc].ansl,t[t[k].rc].ansl); t[k].ansl=max(t[k].ansl,t[t[k].rc].smax-t[t[k].lc].smin); t[k].ansr=max(t[t[k].lc].ansr,t[t[k].rc].ansr); t[k].ansr=max(t[k].ansr,t[t[k].lc].smax-t[t[k].rc].smin); } void Build(int ll,int rr) { int k=++num; t[k].l=ll;t[k].r=rr; if(ll==rr) { t[k].smin=t[k].smax=a[ll]; return; } t[k].lc=num+1; Build(ll,(ll+rr)/2); t[k].rc=num+1; Build((ll+rr)/2+1,rr); update(k); } int findmin(int k,int ll,int rr) { if(ll<=t[k].l&&rr>=t[k].r)return t[k].smin; int mid=(t[k].l+t[k].r)/2; if(rr<=mid)return findmin(t[k].lc,ll,rr); else if(ll>mid)return findmin(t[k].rc,ll,rr); else return min(findmin(t[k].lc,ll,mid),findmin(t[k].rc,mid+1,rr)); } int findmax(int k,int ll,int rr) { if(ll<=t[k].l&&rr>=t[k].r)return t[k].smax; int mid=(t[k].l+t[k].r)/2; if(rr<=mid)return findmax(t[k].lc,ll,rr); else if(ll>mid)return findmax(t[k].rc,ll,rr); else return max(findmax(t[k].lc,ll,mid),findmax(t[k].rc,mid+1,rr)); } int findl(int k,int ll,int rr) { if(ll<=t[k].l&&rr>=t[k].r)return t[k].ansl; int mid=(t[k].l+t[k].r)/2; if(rr<=mid)return findl(t[k].lc,ll,rr); else if(ll>mid)return findl(t[k].rc,ll,rr); else { int maxx=0; maxx=max(findl(t[k].lc,ll,mid),findl(t[k].rc,mid+1,rr)); maxx=max(maxx,findmax(t[k].rc,mid+1,rr)-findmin(t[k].lc,ll,mid)); return maxx; } } int findr(int k,int ll,int rr) { if(ll<=t[k].l&&rr>=t[k].r)return t[k].ansr; int mid=(t[k].l+t[k].r)/2; if(rr<=mid)return findr(t[k].lc,ll,rr); else if(ll>mid)return findr(t[k].rc,ll,rr); else { int maxx=0; maxx=max(findr(t[k].lc,ll,mid),findr(t[k].rc,mid+1,rr)); maxx=max(maxx,findmax(t[k].lc,ll,mid)-findmin(t[k].rc,mid+1,rr)); return maxx; } } int main() { n=init(); for(int i=1;i<=n;i++) a[i]=init(); for(int i=1;i<=maxn*2;i++) t[i].smin=inf; Build(1,n); int x,y; m=init(); for(int i=1;i<=m;i++) { x=init();y=init(); if(x==y) { printf("0 "); continue; } if(x<y)printf("%d ",findl(1,x,y)); else printf("%d ",findr(1,y,x)); } return 0; }