#include <iostream>
#include <fstream>

using namespace std;

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

int N, a[100000];

void read()
{
    f >> N;
    for (int i = 0; i < N; ++i)
        f >> a[i];
}

int binara1(int x)
{
    int st = 0;
    int dr = N-1;

    while (dr - st > 1)
    {
        int mij = (st + dr) / 2;

        if (x > a[mij])
            st = mij;
        if (x < a[mij])
            dr = mij;

        if (x == a[mij])
        {
            while (x == a[mij])
                mij++;
            return mij;
        }
    }

    return -1;
}

int binara2(int x)
{
    int st = 0;
    int dr = N-1;
    int pos;
    while (dr - st > 1)
    {
        int mij = (st + dr) / 2;
        pos = mij;
        if (x > a[mij])
            st = mij;
        if (x < a[mij])
            dr = mij;
        if (x == a[mij])
            break;
    }

    while (a[pos] <= x)
        pos++;

    return pos;
}

int binara3(int x)
{
    int st = 0;
    int dr = N-1;
    int pos;

    while (dr - st > 1)
    {
        int mij = (st + dr) / 2;
        pos = mij;

        if (x > a[mij])
            st = mij;
        if (x < a[mij])
            dr = mij;
        if (x == a[mij])
            break;
    }

    while (a[pos] >= x)
        pos--;

    return pos+2;
}

int main()
{
    read();

    int k;
    f>>k;
    for (int o = 0; o < k; ++o)
    {
        int instr, val;
        f >> instr >> val;
        if (instr == 0)
            g << binara1(val) << endl;
        else if (instr == 1)
            g << binara2(val) << endl;
        else g << binara3(val) << endl;
    }
    return 0;
}