#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 > 0)
    {
        int mij = (st + dr) / 2;

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

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

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

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

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

        if (x <= a[mij])
            dr = mij-1;
        else
            st = mij+1;
    }
    if (a[st] < x)
        st++;
    return st + 1;
}

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;
}