/*这一道题是有一排商店，可以买水果也可以卖水果，买水果和卖水果的价钱一样。 问你从商店x走到商店y，买卖所得最大收益是多少。 我们可以发现朴素的办法是一路扫过去，记录当前最小值，然后更新收益。 这样应该会T（我没试过） 这样丢失了很多信息。 我们考虑一下能不能存起来。 发现解满足区间加法。 即【L，R】中最大的收益要么是【L，K】中的收益，要么是【K，R】中的收益（端点重合不影响），要么是【K，R】中的最大值减去【L，K】中的最小值。这是针对从左往右走的。 于是乎我们可以用线段树来维护这些信息。 因为我们有可能从左往右走，也可能从右往左走，所以记个f数组，f[0]表示从线段树中下标小的向下标大的走所得的最大收益。 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 200010#define inf 0x7fffffffusing 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\n");                continue;          }        if(x<y)printf("%d\n",findl(1,x,y));        else printf("%d\n",findr(1,y,x));      }    return 0;}