#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define inf 0x3f3f3f3f
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}
int n,m,flag=0;
struct segmenttree{
    int ls[N<<2],rs[N<<2],l[N<<2],r[N<<2],v[N<<2],tag[N<<2];
    int tot;
    void push_down(int x){
        if(!tag[x])return;
        tag[ls[x]]+=tag[x];tag[rs[x]]+=tag[x];
        v[ls[x]]+=tag[x];v[rs[x]]+=tag[x];tag[x]=0;
    }
    void push_up(int x){
        v[x]=min(v[ls[x]],v[rs[x]]);
    }
    void build(int &x,int L,int R){
        x=++tot;l[x]=L;r[x]=R;if(L==R)return v[x]=0,void();
        int mid=(L+R)>>1;build(ls[x],L,mid);build(rs[x],mid+1,R);
        push_up(x);
    } 
    void update(int x,int L,int R,int val){
        //cerr<<l[x]<<' '<<r[x]<<' '<<L<<' '<<R<<' '<<val<<' '<<v[x]<<' '<<x<<endl;
        if(L<=l[x] && r[x]<=R)return v[x]+=val,tag[x]+=val,void();
        int mid=(l[x]+r[x])>>1;push_down(x);
        if(L<=mid)update(ls[x],L,R,val);
        if(R>mid)update(rs[x],L,R,val);
        push_up(x);
    }
    int query(int x,int p){
        if(l[x]==r[x])return flag=(v[x]==0),l[x];
        if(r[x]<=p && v[x])return 0;
        push_down(x);int ans=0;
        if(l[rs[x]]<=p)ans=query(rs[x],p);
        if(flag)return ans;
        else return query(ls[x],p);
    }
    int ask(int x,int p){
        if(l[x]==r[x])return v[x];
        push_down(x);int mid=(l[x]+r[x])>>1;
        if(p<=mid)return ask(ls[x],p);
        else return ask(rs[x],p);
    }
}T;
int tot=0;
struct Node{
    int l,r,val;
    Node(int l=0,int r=0,int val=0):l(l),r(r),val(val){}
};
Node stamin[N],stamax[N],sta[N],info[N];
int tp1,tp2,a[N],tp,clo[N];
int consec(Node u,Node v){
    if(u.r+1==v.l)return 1;
    else if(v.r+1==u.l)return 2;
    else return 0;
}
vector<int> e[N];
void add(int u,int v){
    //cerr<<u<<' '<<v<<endl;
    e[u].push_back(v);
}
int con[N],rsonl[N];
void build(){
    for(int i=1;i<=n;i++)if(abs(a[i]-a[i+1])==1)con[i]=1;
    stamin[++tp1]=Node(1,1,a[1]);stamax[++tp2]=Node(1,1,a[1]);
    T.update(1,1,n,-1);sta[++tp]=Node(a[1],a[1],1);tot=n;clo[1]=3;info[1]=Node(1,1,0);
    T.update(1,1,1,1);
    for(int i=2;i<=n;i++){
        T.update(1,1,n,-1);int l=i;clo[i]=3;
        T.update(1,i,i,i);
        //cerr<<stamin[tp1].val<<' '<<a[i]<<endl;
        while(tp1 && stamin[tp1].val>a[i]){
            //cerr<<stamin[tp1].l<<' '<<l-1<<' '<<a[i]-stamin[tp1].val<<endl;
            T.update(1,stamin[tp1].l,l-1,stamin[tp1].val-a[i]);
            l=stamin[tp1].l;tp1--;
        }
        stamin[++tp1]=Node(l,i,a[i]);l=i;
        while(tp2 && stamax[tp2].val<a[i]){
            //cerr<<stamax[tp2].l<<' '<<l-1<<' '<<a[i]-stamax[tp2].val<<endl;
            T.update(1,stamax[tp2].l,l-1,a[i]-stamax[tp2].val);
            l=stamax[tp2].l;tp2--;
        }
        stamax[++tp2]=Node(l,i,a[i]);
        sta[++tp]=Node(a[i],a[i],i);info[i]=Node(i,i,0);
        while(tp!=1){
            Node u=sta[tp],v=sta[tp-1];
            int vali=consec(v,u);
            //cerr<<rsonl[v.val]<<endl;
            if(clo[v.val] && e[v.val].size() && T.ask(1,rsonl[v.val])==0){
                rsonl[v.val]=info[u.val].l;
                add(v.val,u.val);tp--;info[v.val].r=info[u.val].r;
            }
            else{
                flag=0;int pos=T.query(1,info[u.val].l-1);
                //cerr<<pos<<endl;
                if(!flag)break;
                else if(pos==info[v.val].l){
                    ++tot;Node np=Node(min(v.l,u.l),max(v.r,u.r),tot);tp-=2;
                    add(tot,v.val);add(tot,u.val);
                    info[tot]=Node(info[v.val].l,info[u.val].r,0);
                    clo[tot]=consec(v,u);sta[++tp]=np;rsonl[tot]=info[u.val].l;
                }
                else{
                    ++tot;int r=0;
                    while(info[sta[tp].val].l!=pos)r=max(r,sta[tp].r),add(tot,sta[tp].val),tp--;
                    //cerr<<tp<<endl;
                    add(tot,sta[tp].val);
                    r=max(r,sta[tp].r);info[tot]=Node(pos,i,0);tp--;
                    sta[++tp]=Node(r-(i-pos-1)+1,r,tot);
                    rsonl[tot]=info[u.val].l;
                }
            }
        }
        //for(int i=1;i<=tp;i++)cerr<<info[sta[i].val].l<<' '<<info[sta[i].val].r<<' ';
        //cerr<<"****"<<endl;
    }
}
int cnt,dfn[N],mi[N][21];
void dfs(int x,int fa){
    //cerr<<x<<' '<<fa<<endl;
    dfn[x]=++cnt;mi[dfn[x]][0]=fa;
    for(auto v:e[x])if(v!=fa)dfs(v,x);
}
int get(int x,int y){
    return (dfn[x]<dfn[y]?x:y);
}
void pre_lca(){
    for(int i=1;i<=__lg(tot);i++){
        for(int j=1;j+(1<<i)-1<=tot;j++){
            mi[j][i]=get(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
        }
    }
}
int lca(int x,int y){
    if(x==y)return x;x=dfn[x];y=dfn[y];
    if(x>y)swap(x,y);x++;
    int d=__lg(y-x+1);
    return get(mi[x][d],mi[y-(1<<d)+1][d]);
}
int getans(int res,int p){
    int l=0,r=e[res].size()-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(info[e[res][mid]].l<=p)l=mid;
        else r=mid-1;
    }
    return e[res][l];
}
int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif
    n=read();int rt;
    for(int i=1;i<=n;i++)a[i]=read();
    T.build(rt,1,n);build();dfs(sta[tp].val,0);pre_lca();m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),res=lca(u,v);
        //cerr<<res<<' '<<info[res].l<<' '<<info[res].r<<' '<<clo[res]<<endl;
        if(u==v){write(u);putchar(' ');write(u);putchar('\n');}
        else if(clo[res]){
            int p1=getans(res,u),p2=getans(res,v);
            //cerr<<info[res].l<<' '<<info[res].r<<endl;
            //cerr<<p1<<' '<<p2<<' '<<info[p1].l<<' '<<info[p1].r<<' '<<info[p2].l<<' '<<info[p2].r<<endl;
            write(info[p1].l);putchar(' ');write(info[p2].r);putchar('\n');
        }
        else{
            write(info[res].l);putchar(' ');write(info[res].r);putchar('\n');
        }
    }
}