#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;
    i=1;
    j=n;
    while(i<=j){
        mid=(i+j)/2; // 1 3 3 3 5
        if(x[mid]==nr) {while(1<2){
                            if(x[mid+1]==nr) mid++;
                            else return mid;
                        }}
        else if(nr<x[mid]) j=mid-1;
             else i=mid+1;
    }
    return -1;
}


int cautbin1(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;
            i=mid+1;
        }
        else if(x[mid]>nr) j=mid-1;
    }
    return k;
}

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;
}