#include <iostream>
#include <fstream>

using namespace std;

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

int n, m, v[100001];

int k1 (int li, int lf, int x) {
    int m;

    while (li <= lf) {
        m = (li + lf) / 2;
        if (v[m] <= x)
            li = m + 1;
        else
            lf = m - 1;
    }
    m = (li + lf) / 2;

    if (v[m] > x)
        m --;
    if (v[m] == x)
        return m;
    return -1;
}

int k2(int li, int lf, int x) {
    int m;

    while (li < lf){
        m = (li + lf) / 2;
        if (v[m] <= x)
            li = m + 1;
        else
            lf = m;
    }
    m = (li + lf) / 2;

    if (v[m] > x)
        m --;
    return m;
}

int k3 (int li, int lf, int x) {
    int m;

    while (li < lf) {
        m = (li + lf) / 2;
        if (v[m] < x)
            li = m + 1;
        else
            lf = m;
    }
    m = (li + lf) / 2;

    if (v[m] < x)
        m ++;
    return m;
}

int main ()
{
    fin>>n;
    for(int i = 1; i <= n; i++)
        fin>>v[i];

    fin>>m;
    while (m){
        int k, x;
        fin>>k>>x;

        if (k == 0)
            fout<<k1(1, n, x)<<"\n";
        if (k == 1)
            fout<<k2(1, n, x)<<"\n";
        if (k == 2)
            fout<<k3(1, n, x)<<"\n";

        m--;
    }

    return 0;
}