#include <bits/stdc++.h>

using namespace std;

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

int n, sir[100001], m, p, x;

void solve0() {
    int mid, st = 1, dr = n;

    while (st <= dr) {
        mid = (st + dr) / 2;

        if (sir[m] <= x)
            st = mid + 1;
        else
            dr = mid - 1;
    }

    mid = (st + dr) / 2;
    if (sir[mid] > x)
        --mid;

    if (sir[mid] == x)
        out << mid << "\n";
    else
        out << -1 << "\n";
}

void solve1() {
    int mid, st = 1, dr = n;

    while (st < dr) {
        mid = (st + dr) / 2;

        if (sir[m] <= x)
            st = mid + 1;
        else
            dr = mid;
    }

    mid = (st + dr) / 2;
    if (sir[mid] > x)
        --mid;

    out << mid << "\n";
}

void solve2() {
    int mid, st = 1, dr = n;

    while (st < dr) {
        mid = (st + dr) / 2;

        if (sir[mid] < x)
            st = mid + 1;
        else
            dr = mid;
    }

    mid = (st + dr) / 2;
    if (sir[mid] < x)
        ++mid;

    out << mid << "\n";
}

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

    in >> m;
    while (m--) {
        in >> p >> x;

        if (p == 0)
            solve0();
        else if (p == 1)
            solve1();
        else
            solve2();
    }
    return 0;
}