#include <bits/stdc++.h>
using namespace std;

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

constexpr int NMAX = 100005;

int powMax(int n) {
    int res = 1;
    while (res * 2 < n) {
        res *= 2;
    }
    return res;
}

int caut0(int arr[], int n, int val) {
    int acc = 0;
    int curPow2 = powMax(n);

    while (curPow2) {
        if (acc + curPow2 < n && arr[acc + curPow2] <= val) {
            acc += curPow2;
        }
        curPow2 /= 2;
    }
    return (arr[acc] == val) ? acc + 1 : -1;
}

int caut1(int arr[], int n, int val) {
    int acc = 0;
    int curPow2 = powMax(n);

    while (curPow2) {
        if (acc + curPow2 < n && arr[acc + curPow2] <= val) {
            acc += curPow2;
        }
        curPow2 /= 2;
    }
    return acc;
}

int caut2(int arr[], int n, int val) {
    int acc = n - 1;
    int curPow2 = powMax(n);

    while (curPow2) {
        if (acc + curPow2 < n && arr[acc - curPow2] >= val) {
            acc -= curPow2;
        }
        curPow2 /= 2;
    }
    return acc;
}

int main() {
    int n;
    int arr[NMAX];

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

    int q, tip, val;
    fin >> q;
    while (q--) {
        fin >> tip >> val;
        if (tip == 0) {
            fout << caut0(arr, n, val) << '\n';
        }
        else if (tip == 1) {
            fout << caut1(arr, n, val) + 1 << '\n';
        }
        else {
            fout << caut2(arr, n, val) + 1 << '\n';
        }
    }
}