#include<bits/stdc++.h>

using namespace std;

struct node{
    int mn,mx;
};

node combine(node n1, node n2){
    node ans;
    ans.mn=min(n1.mn,n2.mn);
    ans.mx=max(n1.mx,n2.mx);
    return ans;
}

node build_from_one(int n){
    node ans;
    ans.mx=n;
    ans.mn=n;
    return ans;
}

node shitty_node;
vector<int> a;
vector<node> t;

void build(int v, int tl, int tr){
    if(tl==tr){
        t[v]=build_from_one(a[tl]);
        return;
    }
    int tm=(tl+tr)/2;
    build(v*2, tl, tm);
    build(v*2+1,tm+1,tr);
    t[v]=combine(t[v*2],t[v*2+1]);
}

node get_ans(int v, int tl, int tr, int r, int l){
    if(l>r){
        return shitty_node;
    }
    if(tl==r and tr==l)
        return t[v];
    int tm=(tl+tr)/2;
    return combine(get_ans(v*2,tl,tm,min(r,tm),l), get_ans(v*2+1,tm+1,tr,r,max(l,tm+1)));
}

int main(){
    shitty_node.mn=1e9;
    shitty_node.mx=-1e9;
    int n;
    cin>>n;
    a.resize(n);t.resize(n*4,shitty_node);
    for(int i=0;i<n;i++)
        cin>>a[i];
    build(0,0,n-1);
    int q;cin>>q;
    while(q--){
        int ll,rr;
        cin>>ll>>rr;ll--;rr--;
        node ans=get_ans(0,0,n-1,rr,ll);
        cout<<ans.mn<<' '<<ans.mx<<'\n';
    }
}