#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 100005 ;

int N, A[NMAX], tip, v;


int cautbin0(int A[], int st, int dr, int v)
{
    int rez = -1 ;

    while(st <= dr)
    {
        int mijloc = (st + dr) / 2 ;

        if(A[mijloc] < v)
            st = mijloc + 1 ;
        else if(A[mijloc] > v)
            dr = mijloc - 1 ;
        else
        {
            rez = mijloc ;
            st = mijloc + 1 ;
        }
    }

    return rez ;
}



int cautbin1(int A[], int st, int dr, int v)
{
    int rez = -1 ;

    while(st <= dr)
    {
        int mijloc = (st + dr) / 2 ;

        if(A[mijloc] <= v)
        {
            rez = mijloc ;
            st = mijloc + 1 ;
        }

        else
        {

            dr = mijloc - 1 ;
        }
    }

    return rez;
}


int cautbin2(int A[], int st, int dr, int v)
{
    int rez = -1 ;

    while(st <= dr)
    {
        int mijloc = (st + dr) / 2 ;

        if(A[mijloc] >= v)
        {
            dr = mijloc - 1 ;
            rez = mijloc ;
        }
        else
        {
            st = mijloc + 1 ;
        }
    }

    return rez ;
}

int main()
{
    ifstream fin("cautbin.in") ;
    ofstream fout("cautbin.out") ;

    fin >> N ;

    for(int i = 1 ; i <= N ; ++ i)
        fin >> A[i] ;

    int t ;

    fin >> t ;

    while(t --)
    {
        fin >> tip >> v ;

        switch (tip){
        case 0:
        fout << cautbin0(A, 1, N, v) << '\n';
        break;
    case 1:
        fout << cautbin1(A, 1, N, v) << '\n';
        break;
    case 2:
        fout << cautbin2(A, 1, N, v) << '\n';
        break;
    default:
        break;}

    }

    fin.close() ;
    fout.close() ;
    return 0;
}