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

int bsearch1(int r,int x,int*ar){
int l=1;int floor;
while(l<=r){
    floor=(l+r)/2;
    if(ar[floor]<=x)l=floor+1; else r=floor-1;
}
floor=(l+r)/2;if(ar[floor]>x)floor--;
if(ar[floor]==x)return floor; else return -1;
}


int bsearch2(int r,int x,int* ar){
int l=1;int floor;
while(l<r){
    floor=(l+r)/2;
    if(ar[floor]<=x)l=floor+1; else r=floor;
}
floor=(l+r)/2;if(ar[floor]>x)floor--;return floor;
}


int bsearch3(int r,int x,int* ar){
int l=1;int floor;
while(l<r){
   floor=(l+r)/2;
   if(ar[floor]<x)l=floor+1;else r=floor;
}
floor=(l+r)/2;if(ar[floor]<x)floor++;return floor;
}


int main(){
int n,m;fin>>n;int ar[n+1];for(int a=1;a<=n;a++)fin>>ar[a];
fin>>m;int g,x;
while(m){
    fin>>g>>x;
    if(g==0){
        fout<<bsearch1(n,x,ar)<<endl;
    }
    if(g==1){
        fout<<bsearch2(n,x,ar)<<endl;
    }
    if(g==2){
        fout<<bsearch3(n,x,ar)<<endl;
    }
m--;
}
return 0;}