#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

long long x[100005];
int m,n;

int cautbin0(int nr){
    int i,j,mid,r=-1;
    i=1;
    j=n;
    while(i<=j){
        mid=(i+j)/2; // 1 3 3 3 5
        if(x[mid]==nr) {r=mid;i=mid+1;}
        else if(nr<x[mid]){j=mid-1;}
             else i=mid+1;
    }
    return r;
}

int cautbin1(int nr){
    int i,j,mid,r=-1;
    i=1;
    j=n;
    while(i<=j){
        mid=(i+j)/2; // 1 3 3 3 5
        if(x[mid]==nr) {r=mid;i=mid+1;}
        else if(nr<x[mid]){j=mid-1;}
             else nr--;
    }
    return r;
}

int cautbin2(int nr){
    int i,j,mid,k;
    i=1;
    j=n;
    while(i<=j){
        mid=(i+j)/2; // 1 2 2   3 4 4 5 6 ---4
        if(nr<=x[mid]){
            k=mid;
            j=mid-1;
        }
        else if(x[mid]<nr) i=mid+1;
    }
    return k;
}
int main()
{
    int i;
    fin >> n;
    for(i=1;i<=n;i++) fin >> x[i];
    fin >> m;
    for(i=1;i<=m;i++){
        int tip , y;
        fin >> tip >> y;
        if(tip==0) fout << cautbin0(y)<< "\n";
        else if(tip==1) fout <<cautbin1(y)<<"\n";
        else if(tip==2) fout <<cautbin2(y)<<"\n";
    }

    return 0;
}