#include <fstream>
#include <vector>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

vector <int> v;

int t, x, n, m;

int cautbin1(int val)
{
    int i = -1;
    int step = 1;

    while (step * 2 < n)
        step *= 2;

    while (step > 0)
    {
        if (i + step < n && v[i + step] <= val)
            i += step;
        step /= 2;
    }
    if(v[i] == val)
        return i;
    else return -1;
}

int cautbin2(int val)
{
    int i = -1;
    int step = 1;

    while (step * 2 < n)
        step *= 2;

    while (step > 0)
    {
        if (i + step < n && v[i + step] <= val)
            i += step;
        step /= 2;
    }
    return i;
}

int cautbin3(int val)
{
    int i = -1;
    int step = 1;

    while (step < n)
    {

        if (i + step < n && v[i + step] >= val)
            i += step;
        step *= 2;
    }
    return i;
}

void citirevector()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        int a;
        fin >> a;
        v.push_back(a);
    }
}

void rezolvare()
{
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> t >> x;
        if(t == 0)
            fout << cautbin1(x) + 1<< "\n";
        else if(t == 1)
            fout << cautbin2(x) + 1 << "\n";
        else fout << cautbin3(x) + 1 << "\n";

    }
}

int main()
{

    citirevector();
    rezolvare();
    return 0;
}