#include<iostream>
#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n, v[10100100], k, x, y, poz;
int cbin1(int a, int b){
int m;
while(a<=b){
m=(a+b)/2;
if(y>=v[m]) {a=m+1; poz=m;}
else b=m-1;
}
poz=b;
if(!poz) return -1;
else return poz;
}

int cbin2(int a, int b){
int m;
while(a<=b){
m=(a+b)/2;
if(y>v[m]) {a=m+1; poz=m;}
else b=m-1;
}
poz=a;
if(!poz) return -1;
else return poz;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; ++i)
        f>>v[i];
    f>>k;
    for(int i=0; i<k; ++i){
        f>>x>>y;
        if(x==0){poz=0;  cout<<cbin1(1, n)<<'\n';}
        else if(x==1) {poz=0; cbin1(1, n); cout<<poz<<'\n';}
        else {poz=0; cbin2(1, n); cout<<poz;}
    }
    return 0;
}