#include<bits/stdc++.h>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

const int Nmax=1e5+1;

int n,m,v[Nmax];

int cb1(int,int,int,int);
int cb2(int,int,int,int);
int cb3(int,int,int,int);

int main(){
    fin>>n;
    for(int i=1;i<=n;i++)
      fin>>v[i];
    fin>>m;
    int t,a;
    for(int i=1;i<=m;i++){
        fin>>t>>a;
        if(t==0) fout<<cb1(1,n,a,n+1)<<'\n';
        else if(t==1) fout<<cb2(1,n,a,n+1)<<'\n';
        else fout<<cb3(1,n,a,n+1)<<'\n';
    }
    return 0;
}

int cb1(int st, int dr, int x,int poz){
    if(st<=dr){
        int m=(st+dr)/2;
        if(v[m]==x) return cb1(m+1,dr,x,m);
        else if(v[m]>x) return cb1(st,m-1,x,poz);
        else return cb1(m+1,dr,x,poz);
    }
    else{
        if(poz==n+1) return -1;
        else return poz;
    }
}
int cb2(int st, int dr, int x,int poz){
    if(st<=dr){
        int m=(st+dr)/2;
        if(v[m]<=x) return cb1(m+1,dr,x,m);
        else return cb1(st,m-1,x,poz);
    }
    else return poz;
}
int cb3(int st, int dr, int x,int poz){
    if(st<=dr){
        int m=(st+dr)/2;
        if(v[m]>=x) return cb1(st,m-1,x,m);
        else return cb1(m+1,dr,x,poz);
    }
    else return poz;
}