#include<bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in"); ofstream fout("cautbin.out");

int n, a[100010];


int bs0(int x, int r, int l){
int m=r+(l-r)/2;
if(r>l){return -1;}

if(a[m]==x && (a[m+1]>x || m+1>n) ){return m;}
else{
if(a[m]>x){return bs0(x, r, m-1);}
else{return bs0(x, m+1, l);}
}

}



int bs1(int x, int r, int l){
int m=r+(l-r)/2;
if(r>l){return -1;}

if(a[m]<=x && (a[m+1]>x || m+1>n) ){return m;}
else{
if(a[m]>x){return bs1(x, r, m-1);}
else{return bs1(x, m+1, l);}
}

}



int bs2(int x, int r, int l){
int m=r+(l-r)/2;
if(r>l){return -1;}

if(a[m]>=x && (a[m-1]<x || m+1>n) ){return m;}
else{
if(a[m]>=x){return bs2(x, r, m-1);}
else{return bs2(x, m+1, l);}
}

}





int main(){
fin>>n;

 for(int i=1; i<=n; i++){
fin>>a[i];
 }
int m, o, x;
fin>>m;

for(;m;m--){
    fin>>o>>x;
    if(o==0){fout<<bs0(x, 1, n)<<"\n";}
    if(o==1){fout<<bs1(x, 1, n)<<"\n";}
    if(o==2){fout<<bs2(x, 1, n)<<"\n";}
}



    return 0;
}