#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<ll>A(N);
    for(auto &x:A)
        cin>>x;
    map<ll,vector<ll>>m;
    for(ll i=0;i<N;i++)
        m[A[i]].push_back(i);
    ll Q;
    cin>>Q;
    while(Q--){
        ll X,Y;
        cin>>Y>>X;
        ll xlo=0;
        ll xhi=sz(m[X]);
        ll xc=xhi;
        if(!xc){
            cout<<"0\n";
            continue;
        }
        ll ylo=0;
        ll yhi=sz(m[Y]);
        ll lo=0;
        ll hi=N;
        while(lo+1<hi){
            ll mid=(lo+hi)>>1;
            ll c1=upper_bound(m[X].begin()+xlo,m[X].begin()+xhi,mid)-m[X].begin();
            ll c2=upper_bound(m[Y].begin()+ylo,m[Y].begin()+yhi,mid)-m[Y].begin();
            if(c1+c2<=xc){
                lo=mid;
                xlo=c1;
                ylo=c2;
            }
            else{
                hi=mid;
                xhi=c1;
                yhi=c2;
            }
        }
        ll ans=upper_bound(all(m[Y]),lo)-m[Y].begin();
        cout<<ans<<'\n';
    }
    return 0;
}