#include <bits/stdc++.h>
#define sz(x) ((ll) (x).size())
#define all(x) (x).begin(), (x).end()
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
int main() {
    FastIO;
    ll N;
    cin>>N;
    vector<array<ll,2>>A(N);
    for(ll i=0;i<N;i++){
        cin>>A[i][0];
        A[i][1]=i;
    }
    sort(all(A));
    ll Q;
    cin>>Q;
    while(Q--){
        ll X,Y;
        cin>>Y>>X;
        array<ll,2>q;
        q[0]=X;
        q[1]=0;
        ll xbeg=lower_bound(all(A),q)-A.begin();
        q[1]=N;
        ll xend=lower_bound(all(A),q)-A.begin();
        ll xlo=0;
        ll xhi=xend-xbeg;
        ll xc=xhi;
        if(!xc){
            cout<<"0\n";
            continue;
        }
        q[0]=Y;
        q[1]=0;
        ll ybeg=lower_bound(all(A),q)-A.begin();
        q[1]=N;
        ll yend=lower_bound(all(A),q)-A.begin();
        ll ylo=0;
        ll yhi=yend-ybeg;
        if(!yhi){
            cout<<"0\n";
            continue;
        }
        ll lo=0;
        ll hi=N;
        ll ans=-1;
        while(lo+1<hi){
            ll mid=(lo+hi)>>1;
            q[0]=X;
            q[1]=mid;
            ll c1=upper_bound(A.begin()+xbeg+xlo,A.begin()+xbeg+xhi,q)-A.begin()-xbeg;
            q[0]=Y;
            ll c2=upper_bound(A.begin()+ybeg+ylo,A.begin()+ybeg+yhi,q)-A.begin()-ybeg;
            if(c1+c2<=xc){
                lo=mid;
                xlo=c1;
                ylo=c2;
                ans=c2;
            }
            else{
                hi=mid;
                xhi=c1;
                yhi=c2;
            }
        }
        if(ans<0)
            ans=A[ybeg][1]<A[xbeg][1];
        cout<<ans<<'\n';
    }
    return 0;
}