/*

线段树开到*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*];

int init()

{

    int x=;char s;bool f=;s=getchar();

    while(s<''||s>'')s=getchar();

    while(s>=''&&s<='')

      {

          x=x*+s-'';

          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+;

    Build(ll,(ll+rr)/);

    t[k].rc=num+;

    Build((ll+rr)/+,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)/;

    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+,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)/;

    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+,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)/;

    if(rr<=mid)return findl(t[k].lc,ll,rr);

    else if(ll>mid)return findl(t[k].rc,ll,rr);

    else

      {

          int maxx=;

          maxx=max(findl(t[k].lc,ll,mid),findl(t[k].rc,mid+,rr));

          maxx=max(maxx,findmax(t[k].rc,mid+,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)/;

    if(rr<=mid)return findr(t[k].lc,ll,rr);

    else if(ll>mid)return findr(t[k].rc,ll,rr);

    else

      {

          int maxx=;

          maxx=max(findr(t[k].lc,ll,mid),findr(t[k].rc,mid+,rr));

          maxx=max(maxx,findmax(t[k].lc,ll,mid)-findmin(t[k].rc,mid+,rr));

          return maxx;

      }

}

int main()

{

    n=init();

    for(int i=;i<=n;i++)

      a[i]=init();

    for(int i=;i<=maxn*;i++)

      t[i].smin=inf;

    Build(,n);

    int x,y;

    m=init();

    for(int i=;i<=m;i++)

      {

          x=init();y=init();

          if(x==y)

            {

                printf("0\n");

                continue;

          }

        if(x<y)printf("%d\n",findl(,x,y));

        else printf("%d\n",findr(,y,x));

      }

    return ;

}