#include <fstream>
using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int n, tip, m, val, a[100010], i;

int cautare0 (int li, int ls, int el)
{
    int mij;

    while (li<=ls)
    {
        mij=(li+ls)/2;

        if (a[mij]<=el)
        {
            li=mij+1;
        }
        else
        {
            ls=mij-1;
        }

    }

    mij=(li+ls)/2;

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

}

int cautare1 (int li, int ls, int el)
{
    int mij;

    while (li<ls)
    {
        mij=(li+ls)/2;

        if (a[mij]<=el)
        {
            li=mij+1;
        }
        else
        {
            ls=mij-1;
        }

    }

    mij=(li+ls)/2;

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

    return mij;

}

int cautare2 (int li, int ls, int el)
{
    int mij;

    while (li<ls)
    {
        mij=(li+ls)/2;

        if (a[mij]<el)
        {
            li=mij+1;
        }
        else
        {
            ls=mij;
        }

    }

    mij=(li+ls)/2;

    if (a[mij]<el)
        mij++;

    return mij;

}







int main ()
{
    f>>n;

    for (i=1; i<=n; i++)
    {
        f>>a[i];
    }

    f>>m;

    for (i=1; i<=m; i++)
    {
        f>>tip>>val;

        if (tip==0)
        {
            g<<cautare0(1, n, val)<<'\n';
        }
        if (tip==1)
        {
            g<<cautare1(1, n, val)<<'\n';
        }
        if (tip==2)
        {
            g<<cautare2(1, n, val)<<'\n';
        }
    }

    return 0;
}