#include <iostream>
#include <fstream>

using namespace std;

long N, M, V[100005];

long BinarySearch0 (long X)
{
    long Left, Middle, Right;
    Left=1;
    Right=N;
    while (Left<=Right)
    {
        Middle=(Left+Right)/2;
        if ((V[Middle]==X)&&(V[Middle+1]>X))
        {
            return Middle;
        }
        if (V[Middle]<=X)
        {
            Left=Middle+1;
        }
        if (V[Middle]>X)
        {
            Right=Middle-1;
        }
    }
    return -1;
}

long BinarySearch1 (long X)
{
    long Left, Middle, Right;
    Left=1;
    Right=N;
    while (Left<=Right)
    {
        Middle=(Left+Right)/2;
        if ((V[Middle]<=X)&&(V[Middle+1]>X))
        {
            return Middle;
        }
        if (V[Middle]<=X)
        {
            Left=Middle+1;
        }
        if (V[Middle]>X)
        {
            Right=Middle-1;
        }
    }
    return Middle;
}

long BinarySearch2 (long X)
{
    long Left, Middle, Right;
    Left=1;
    Right=N;
    while (Left<=Right)
    {
        Middle=(Left+Right)/2;
        if ((V[Middle]>=X)&&(V[Middle-1]<X))
        {
            return Middle;
        }
        if (V[Middle]<X)
        {
            Left=Middle+1;
        }
        if (V[Middle]>=X)
        {
            Right=Middle-1;
        }
    }
    return Middle;
}

int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    long i, Tip, Cautat;
    fin >> N;
    for (i=1; i<=N; i++)
    {
        fin >> V[i];
    }
    fin >> M;
    for (i=0; i<M; i++)
    {
        fin >> Tip >> Cautat;
        if (Tip==0)
        {
            fout << BinarySearch0 (Cautat) << "\n";
        }
        if (Tip==1)
        {
            fout << BinarySearch1 (Cautat) << "\n";
        }
        if (Tip==2)
        {
            fout << BinarySearch2 (Cautat) << "\n";
        }
    }
    fin.close ();
    fout.close ();
    return 0;
}