#include <fstream>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int v[100001];

int main(){
    int n,m,x,y;
    cin>>n;
    for(int i=1; i<=n; ++i)
        cin>>v[i];
    cin>>m;
    for(int i=1; i<=m; ++i){
        int st,dr,mid,deafis;
        st=1,dr=n,deafis=-1;
        cin>>x>>y;
        if(x==0){
            while(st<=dr){
                mid=(st+dr)/2;
                if(v[mid]==y){
                    deafis=mid;
                    st=mid+1;
                }
                else
                    if(y<v[mid])
                    dr=mid-1;
                else
                    st=mid+1;
            }
            cout<<deafis<<endl;
        }
        else if(x==1){
                while(st<=dr){
                    mid=(st+dr)/2;
                    if(v[mid]<=y){
                        deafis=mid;
                        st=mid+1;
                    }
                    else
                        dr=mid-1;
                }
            cout<<deafis<<endl;
        }
        else{
            while(st<=dr){
                mid=(st+dr)/2;
                if(v[mid]>=y){
                    deafis=mid;
                    dr=mid-1;
                }
                else
                    st=mid+1;
            }
            cout<<deafis<<endl;
        }
    }
    return 0;
}