#include <iostream>
#include <fstream>

using namespace std;
const int NMAX = 100000;
int n;
int m;
int a[NMAX];
int type, val;

int binaryFor0(int k);
int binaryFor1(int k);
int binaryFor2(int k);


int main()
{

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

    fin >> n;

    for(int i=1; i<=n; i++)
    {
         fin >> a[i];

    }
    fin >> m;
    for(int i=0; i<m; i++)
    {
        fin >> type >> val;

        switch(type)
        {

            case 1: fout << binaryFor1(val) << '\n';break;
            case 2: fout << binaryFor2(val) << '\n';break;
            default: fout << binaryFor0(val) << '\n';break;


        }

    }

    fin.close();
    fout.close();
    return 0;
}
int binaryFor2(int k)
{
    int st = 1;
    int dr = n;
    int mij;

    do
    {
        mij  =  st + (dr-st)/2;

        if(a[mij] >= k)
            dr = mij -1;
        else
            st = mij + 1;


    }
    while(st <= dr);


        if(a[mij] < k) mij++;
    return mij;

}
int binaryFor1(int k)
{

    int st = 1;
    int dr = n;
    int mij;

    do
    {
        mij  =  st + (dr-st)/2;

        if(a[mij] > k)
            dr = mij -1;
        else
            st = mij + 1;

           if(a[mij] > k) mij--;


    }
    while(st <= dr);



    return mij;

}
int binaryFor0(int k)
{
    int st = 1;
    int dr = n;
    int mij;

    do
    {
        mij  =  st + (dr-st)/2;

        if(a[mij] > k)
            dr = mij -1;
        else
            st = mij + 1;


    }
    while(st <= dr);

    if (a[mij] > k) mij --;
    if (a[mij] == k)
        return mij;
    return -1;






}