#include <iostream>
#include <fstream>
using namespace std;
int v[100000];
int main(){
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    long long n,m2,st=1,dr,t,x,m=0,poz=-1;
    cin>>n;
    dr=n;
    for(int i=1; i<=n; ++i) cin>>v[i];
    cin>>m2;
    for(int i=1; i<=m2; ++i){
        cin>>t>>x;
        if(t==0){
            while(st<=dr){
                m=(st+dr)/2;
                if(v[m]==x)
                    if(m>poz)
                        poz=m;
                if(x>=v[m])
                    st=m+1;
                else
                    dr=m-1;
            }
            cout<<poz<<"\n";
        }
        else if(t==1){
            while(st<=dr){
                m=(st+dr)/2;
                if(v[m]<=x)
                    if(m>poz)
                        poz=m;
                if(x>=v[m])
                    st=m+1;
                else
                    dr=m-1;
            }
            cout<<poz<<"\n";
        }
        else{
            poz=500000;
            while(st<=dr){
                m=(st+dr)/2;
                if(v[m]>=x)
                    if(m<poz)
                        poz=m;
                if(x<=v[m])
                    dr=m-1;
                else
                    st=m+1;
            }
            cout<<poz<<"\n";
        }
        poz=-1;
        st=1;
        dr=n;
    }
    return 0;
}