#include <bits/stdc++.h>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
///Cauta cel mai mare numar din vector care e strict mai mic decat x. Daca nu exista afiseaza nu exista.
///0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
///1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
///2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x

int n,m,op,x;
int v[100005];

int caz1(int x){
    int inc=1,sf=n,mijl, rez=-1;
    if(v[sf]==x)
        return sf;
    while(inc<=sf)
    {
        mijl= (inc+sf)/2;
        if(v[mijl]==x)
        {
            rez = mijl;
            inc=mijl+1;
        }
        else
        {
            if(v[mijl]<x)
                inc=mijl+1;
            else{sf=mijl-1;}
        }
    }
    return rez;
}

int caz2(int x){
    int inc=1, sf=n, mijl, rez;
    while(inc<=sf)
    {
        mijl = (inc+sf)/2;
        if(v[mijl]>x)
            sf= mijl-1;
        else{
            rez = mijl;
            inc=mijl+1;
        }
    }
    return rez;
}

int caz3(int x){
        int inc=1, sf=n, mijl, rez;
    while(inc<=sf)
    {
        mijl = (inc+sf)/2;
        if(v[mijl]>=x)
        {rez= mijl;
            sf= mijl-1;}
        else{
            inc=mijl+1;
        }
    }
    return rez;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    fin>>m;
    for(int i=0;i<m;i++){
        fin>>op>>x;
        if(op==0){
            fout<<caz1(x);
        }
        if(op==1){
            fout<<caz2(x);
        }
        if(op==2){
            fout<<caz3(x);
        }
        fout<<"\n";
    }
/*    int v[100]={10,10,10,10,10,10,10}, mijl, x=10, inc=0, sf=6, rez=0;
    while(inc<=sf)
    {
        mijl = (inc+sf)/2;
        if(v[mijl]>=x)
            sf= mijl-1;
        else
        {
            rez= v[mijl];
            inc=mijl+1;
        }
    }
    if(rez == 0)
        cout<<"nu exista";
    else
        cout<<rez;
        */
    return 0;
}