#include<iostream>
#include<fstream>
const int dim=100002;
using namespace std;
int v[dim],N,M;

int caut0(int x){
int m,s=1,d=N,g=0;
while(s<=d){
    m=(s+d)/2;
    if(x==v[m]){g=1;if(s==d)return s;else s=m+1;}
    else if(x>v[m])s=m+1;
    else d=m-1;}
    if(g)return s-1;
    return -1;
}


int caut1(int x){
int m,s=1,d=N,g=0;
while(s<=d){
    m=(s+d)/2;
    if(x==v[m]){g=1;if(s==d)return s;else s=m+1;}
    else if(x>v[m])s=m+1;
    else d=m-1;}
    return s-1;
}

int caut2(int x){
int m,s=1,d=N,g=0;
while(s<=d){
    m=(s+d)/2;
    if(x==v[m]){g=1;if(s==d)return s;else d=m-1;}
    else if(x>v[m])s=m+1;
    else d=m-1;}
    return d+1;
}


int main(){int i,nr,x;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

in>>N;
for(i=1;i<=N;i++)in>>v[i];
in>>M;
for(i=1;i<=M;i++){in>>nr>>x;

if(nr==0)out<<caut0(x)<<"\n";

if(nr==1)out<<caut1(x)<<"\n";

if(nr==2)out<<caut2(x)<<"\n";

}
in.close();
out.close();
return 0;
}