#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;
    while( hi - lo > 1)         //cat timp distanta e mai mare ca 1 adica pentru a evita lo=4 hi =5 si mij = 4 si va fi bucla
    {
         mij = lo + (hi - lo)/2;       //alegem mjlocul intervalului [lo,hi] fara overload
         if ( v[ mij ] <= x)           //daca elementul este <= x atunci ne putem uita in dreapta(lo = mij) dar nu sarim peste
            lo = mij;                  //mij doarece el poate fi ultmul element x in cazul in care v[mij] == x
         else
            hi = mij-1;                //altfel (hi = mij-1)stim ca v[mij]>x deci putem sa ignoram toata dreapta
    }
    if (v[ hi ] > x)                   //deci am ramas cu 3 cazuri posibile v[hi]=x sau v[lo]=x sau x nu e
        hi--;                          //daca v[hi]>x inseamna ca daca x exista sigur se afla pe v[hi=(lo)] deci hi--
                                        // //altfel v[hi]  sa fie =x
    if( v[ hi ] == x )                 //deci daca v[hi] == x atunci hi e cea mai mare pozitie si o afisam altfel
        return hi;
    return -1;                          //nu exista deci afisa -1


}
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
    if(v[lo] <= x)
        return lo;                           //deci returnam cealalata pozitie adica lo
    return -1;                              //acoperim si cazul cand nu se gaseste
}
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
    if( v[hi] >= x)                 //acoperim si cazul cand nu se gaseste
        return hi;
    return -1;
}
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;
    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;
}