#include <iostream>
#include <fstream>
using namespace std;
int n,m,v[100003];
int mij;
int binary0(int x)//cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca nu se gaseste
{
    int lo = 1, hi = n;
    int pos = -1;
    while(lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        
        if (v[mid] <= x) {
            pos = mid;
            lo = mid + 1;
        }
        if (v[mid] > x) {
            hi = mid - 1;
        }
    }

        return pos;


}
int binary1(int 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

    int lo = 1, hi = n;                 //algoritmul este asemanator cu cel de a cauta cea mai mare pozitie pe care se
    while(  hi - lo >1)                 //gaseste x
    {
        mij = lo + ( hi - lo )/2;
        if ( v[ mij ] <= x )
            lo = mij;
        else
            hi = mij-1;
    }
    if( v[ hi ] <= x )                   //daca v[hi]>x nu e bine doarece ne trebuie v[hi]<=x deci sigur o sa fie pe hi-1=lo
        return hi;                       //valoarea dorita
    return lo;                           //deci returnam cealalata pozitie adica lo
}
int binary2(int 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 lo = 1, hi = n;
    while( hi - lo >1)
    {
        mij = (lo+hi)/2;           //pana aici este similar cu primii 2 algoritmi
        if ( v[ mij ] < x )        //aici vedem daca elementul current v[mij]<x adica daca elementul curent <x inseamna ca
            lo = mij+1;             //suntem prea in stanga deci automat nu ne mai intereseaz apartea aia ca sigur
        else                       //o sa gasim in cealalta parte un element a.i v[mij] >=x asa ca lo= mij+1
            hi = mij;               //altfel v[mij]>=x deci pozitia dorita se afla in intervalu [lo,mij] si
    }                               // lo =mij tinem cont ca lo nu devine mij-1 deoarece am putea aveae v[mij-1] < x
    //si nu am mai avea elementul dorit
    if( v[ lo ] >= x )              //cea mai mica pozitie o sa fie lo sau hi in cazu in care v[lo]<x
        return lo;                  //deci daca v[lo]>=x atunci stim sigur ca lo e pozitia dorita altfel sigur e lo+1
    return hi;
}
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main()
{
    in>> n;
    for(int i = 1 ; i <= n ; i++)
        in >> v[i];
    in >> m;
    int op,x;
    cout<<m;
    while( m> 0)
    {
        in >> op >> x;
        switch(op)
        {
            case 0 : out<<binary0(x)<<'\n'; break;
            case 1 : out<<binary1(x)<<'\n'; break;
            case 2 : out<<binary2(x)<<'\n'; break;
        }
        m--;
    }
    return 0;
}