#include <iostream>
#include <fstream>

int n, v[100005];
int m;

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

int cauta_0 (int x) {
    int st = 1;
    int dr = n;

    int mijloc;
    while (st <= dr) {
        mijloc = (st + dr)/2;
        if (v[mijloc] == x) {
            if (v[mijloc+1] == x) st = mijloc + 1;
            else return mijloc;
        } else {
            if (v[mijloc] < x) st = mijloc + 1;
            else dr = mijloc - 1;
        }
    }
    return -1;
}

int cauta_1 (int x) {
    int st = 1;
    int dr = n;

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

    }
    return -1;
}

int cauta_2 (int x) {
    int st = 1;
    int dr = n;

    int mijloc;
    while (st <= dr) {
        mijloc = (st + dr)/2;
        if (v[mijloc] >= x)
        {
            if  (v[mijloc -1] >= x and mijloc - 1 > 0) dr = mijloc - 1;
            else return mijloc;
        } else st = mijloc + 1;
    }
    return -1;
}

int main() {


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

    fin >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        fin >> a >> b;
//        std :: cout << a <<" " << b;
        if (a == 0) fout << cauta_0(b) << '\n';
        else if (a == 1) fout << cauta_1(b) << '\n';
        else fout << cauta_2(b) << '\n';
        }
    return 0;
}