#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int v[100001], n;

int CautBin0(int x)
{
    int st, dr, mij, poz;
    poz = -1;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] <= x)
        {
            if (v[mij] == x)
                poz = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return poz;
}

int CautBin1(int x)
{
    int st, dr, mij, poz = -1;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] <= x)
        {
            poz = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return poz;
}

int CautBin2(int x)
{
    int st, dr, mij, poz = -1;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] >= x)
        {
            poz = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return poz;
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    int q;
    fin >> q;
    for (int i = 1; i <= q; i++)
    {
        int tip, x;
        fin >> tip >> x;
        if (tip == 0)
            fout << CautBin0(x) << "\n";
        else if (tip == 1)
            fout << CautBin1(x) << "\n";
        else fout << CautBin2(x) << "\n";
    }
    return 0;
}