#include <iostream>
#include <fstream>

using namespace std;

long binKer_0(long a[], long x, int n)
{
    int bal=1, jobb=n, k;
    while(bal<=jobb){
        k=(bal+jobb)/2;
        if(x<a[k]) jobb=k-1;
        else if(x>a[k]) bal=k+1;
             else{
                int k2=k;
                while(a[k]==a[k2]){
                    k2++;
                }
                return k2-1;
             }
    }
    return -1;
}

int binKer_1(long a[], long x, int n)
{
    int bal=1, jobb=n, k;
    while(bal<jobb){
        k=(bal+jobb)/2;
        if(a[k]<=x) bal=k+1;
        else jobb=k;
    }
    k=(bal+jobb)/2;
    if(a[k]>x) k--;
    return k;
}

int binKer_2(long a[], long x, int n)
{
    int bal=1, jobb=n, k;
    while(bal<jobb){
        k=(bal+jobb)/2;
        if(a[k]<x) bal=k+1;
        else jobb=k;
    }
    k=(bal+jobb)/2;
    if(a[k]<x) k++;
    return k;
}


int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int n, m;
    long x, l;
    in>>n;
    long a[n+1];
    for(int i=1; i<=n; i++) in>>a[i];
    in>>m;
    for(int i=1; i<=m; i++){
        in>>l; in>>x;
        if(l==0) out<<binKer_0(a, x, n)<<endl;
        if(l==1) out<<binKer_1(a, x, n)<<endl;
        if(l==2) out<<binKer_2(a, x, n)<<endl;
    }
    return 0;
}