#include <iostream>
#include <fstream>

using namespace std;

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

int v[100005];
int key;

int bsearch0 (int lo, int hi) {
    int div = lo + (hi - lo) / 2;
    while (lo <= hi) {
        div = lo + (hi - lo) / 2;
        if (v[div] <= key) {
            lo = div + 1;
        }
        else {
            hi = div - 1;
        }
    }
    div = lo + (hi - lo) / 2;
    if (v[div] > key) div --;
    if (v[div] == key) return div;
    return -1;
}

int bsearch1 (int lo, int hi) {
    int div;
    while (lo < hi) {
        div = lo + (hi-lo)/2;
        if (v[div] <= key) {
            lo = div + 1;
        }
        else {
            hi = div;
        }
    }
    div = lo + (hi-lo)/2;
    if (v[div] > key) div--;
    return div;
}

int bsearch2(int lo, int hi) {
    int div;
    while (lo < hi) {
        div = lo + (hi-lo)/2;
        if (v[div] < key) {
            lo = div + 1;
        }
        else {
            hi = div;
        }
    }
    div = lo + (hi-lo)/2;
    if (v[div]<key) div ++;
    return div;
}

int main()
{
    int m, n;
    fin >> n;

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

    fin >> m;

    short int x;
    for (int i=1; i<=m; i++) {
        fin >> x >> key;
        if (x == 0) fout << bsearch0(1, n) << '\n';
        else if (x==1) fout << bsearch1(1, n) << '\n';
        else fout << bsearch2(1, n) << '\n';
    }

    return 0;
}