#include <fstream>

const int NMAX = 100005;

using namespace std;

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

int cautare0(int v[], int N, int x)
{
    int ls = 1;
    int ld = N;

    int mid;

    int pos = -1;

    while(ls <= ld)
    {
        mid = (ls + ld) / 2;

        if (v[mid] == x)
        {
            pos = mid;
            ls = mid + 1;
        }
        else if (v[mid] < x)
        {
            ls = mid + 1;
        }
        else
        {
            ld = mid - 1;
        }
    }

    return pos;
}

int cautare1(int v[], int N, int x)
{
    int ls = 1;
    int ld = N;

    int mid;
    int pos;

    while(ls <= ld)
    {
        mid = (ls + ld) / 2;

        if (v[mid] <= x)
        {
            pos = mid;
            ls = mid + 1;
        }
        else
        {
            ld = mid - 1;
        }
    }

    return pos;
}

int cautare2(int v[], int N, int x)
{
    int ls = 1;
    int ld = N;

    int mid;

    int pos = -1;

    while(ls <= ld)
    {
        mid = (ls + ld) / 2;

        if (v[mid] >= x)
        {
            pos = mid;
            ld = mid - 1;
        }
        else
        {
            ls = mid + 1;
        }
    }

    return pos;
}

int N,M,x,tip;
int v[NMAX];

int main()
{
    f >> N;

    for (int i = 1; i <= N; ++i)
    {
        f >> v[i];
    }

    f >> M;

    for (int i = 1; i <= M; ++i)
    {
        f >> tip >> x;
        if (tip == 0)
        {
            g << cautare0(v, N, x);
            //return 1;
        }
        else if (tip == 1)
        {
            g << cautare1(v, N, x);
            //return 2;
        }
        else if (tip == 2)
        {
            g << cautare2(v, N, x);
            //return 3;
        }

        g << "\n";
    }

    return 0;
}