#include <iostream>
#include <cmath>
#include <fstream>

#define N 100100

int v[N];

int caut_bin_1(int s, int f, int key)
{
    int m;
    while (s <= f)
    {
        m = (s + f) / 2;
        if (v[m] <= key)
            s = m + 1;
        else
            f = m - 1;
    }
    m = (s + f) / 2;
    if (v[m] > key)
        m--;
    if (v[m] == key)
        return m;
    return -1;
}
int caut_bin_2(int s, int f, int key)
{
    int m;
    while (s < f)
    {
        m = (s + f) / 2;
        if (v[m] <= key)
            s = m + 1;
        else
            f = m;
    }

    m = (f + s) / 2;
    if (v[m] > key)
        m--;
    return m;
}
int caut_bin_3(int s, int f, int key)
{
    int m;
    while (s < f)
    {
        m = (s + f) / 2;
        if (v[m] < key)
            s = m + 1;
        else
            f = m;

    }

    m = (f + s) / 2;
    if (v[m] < key)
        m++;
    return m;
}

using namespace std;

int main()
{
    int n, m, tip, val;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    fin >> m;
    while (m--)
    {
        fin >> tip >> val;
        if (tip == 0)
            fout << caut_bin_1(1,n,val) << std::endl;
        if (tip == 1)
            fout << caut_bin_2(1, n, val) << std::endl;
        if (tip == 2)
            fout << caut_bin_3(1, n, val) << std::endl;
    }
    return 0;
}