#include<iostream>
#include<fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
 int v[100005];

int cautare_binara0(int l, int r, int x)
{
    int mijloc;
// atata timp cat capatul din stanga este mai mic decat cel din dreapta
    while(l <= r)
    {

        mijloc = ( l + r) / 2;
        //daca elementul de pe pozitia din stanga este mai mic sau egal cu x, ma mut in partea din dreapta a vectorului
        if( v[mijloc] <= x)
            l = mijloc + 1;
        //altfel, ma mut in partea din stanga a vectorului
        else r = mijloc - 1;
    }
    //cand ies din while mai calculez o data mijlocul cu noile valori pt l si r
    mijloc =  (l + r) / 2;
    //daca totusi valoarea elementului de pe poz din mijlioc este mai mare decat x, scad mijlocul cu o pozitie
    if ( v[mijloc] > x) mijloc --;
    //daca ajung cu v[mijloc]==x atunci returnez pozitia
    if(v[ mijloc] == x) return mijloc;
    //altfel inseamna ca nu exista in sirul dat si returnez -1, ca in cerinta
    else return -1;

}
int cautare_binara1( int l, int r, int x)
{
    int mijloc;

    while(l < r)
    {
        mijloc = ( l + r) / 2;
        //ma mut in partea din dreapta a vectorului
        if( v[mijloc] <= x)
            l = mijloc + 1;
        //altfel ma mut in partea din stanga a vectorului
        else r = mijloc ;
    }
    mijloc = ( l + r) / 2;
    //daca valoarea cautata este mai mica decat elementul de pe pozitia din mijloc scad mijlocul
    if( v[mijloc] > x)
        mijloc --;
    return mijloc;
}
int cautare_binara2( int l, int r, int x)
{
    int mijloc;
//cat timp l nu devine mai mare sau egal cu r
    while(l < r)
    {
        mijloc = ( l + r) / 2;
        //ma mut in partea din dreapta a vectorului
        if( v[mijloc] < x)
        l = mijloc + 1;
        //altfel ma mut in partea din stanga a vectorului
        else r = mijloc ;
    }
    mijloc = ( l + r) / 2;
    if( v[mijloc] < x)
        //daca elementul cautat este mai mare decat v[mijloc], cresc mijlocul
        mijloc ++;
    return mijloc;
}
int main()
{
    int n, m, x, cod, i;
    f >> n;
    for(i = 1; i <=n; i++)
        f >> v[i];
    f >> m;
    for( i = 1; i <= m; i++)
    {
        f >> cod >> x;
        //pentru fiecare cod in parte, 0, 1 sau 2 apelez un alt subprogram
        if( cod == 0) g << cautare_binara0( 1, n, x) << '\n';
        else if (cod == 1) g << cautare_binara1( 1, n, x) << '\n';
        else if( cod == 2) g << cautare_binara2( 1, n, x) << '\n';
    }

return 0;

}