#include <iostream>
#include <fstream>

using namespace std;

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

int n, m, v[100005];

void cautbin0(int a)
{
    int st = 0, dr = n - 1, poz = 0;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (v[mij] <= a)
        {
            st = mij + 1;
            poz = mij;
        }
        else {
            dr = dr - 1;
        }
    }
    if (v[poz] != a)
    {
        g << -1 << '\n';
    }
    else {
        g << poz + 1 << '\n';
    }
}

void cautbin1(int a)
{
    int st = 0, dr = n - 1, poz = -1;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (v[mij] <= a)
        {
            st = mij + 1;
            poz = mij;
        }
        else {
            dr = dr - 1;
        }
    }
    g << poz + 1 << '\n';
}

void cautbin2(int a)
{
    int st = 0, dr = n - 1, poz = -1;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (v[mij] >= a)
        {
            poz = mij;
            dr = mij-1;
        }else{
            st = mij + 1;
        }
    }
    g << poz + 1 << '\n';
}
int main()
{
    f >> n;
    for (int i = 0; i < n; i++)
    {
        f >> v[i];
    }
    f >> m;
    for (int i = 1; i <= m; i++)
    {
        int q, nr;
        f >> q >> nr;
        if (q == 0)
        {
            cautbin0(nr);
        }
        else if (q == 1)
        {
            cautbin1(nr);
        }
        else {
            cautbin2(nr);
        }
    }
    return 0;
}