#include <iostream>
#include <fstream>
#include <vector>

int binary_0(std::vector<int> &myV, int val, int left, int right) {
    if (left >= right) {
        if (myV[left] != val) {
            return -1;
        }
        return left + 1;
    }
    int m = left + (right - left) / 2;
    if (myV[m] > val) {
        return binary_0(myV, val, left, m - 1);
    }
    return binary_0(myV, val, m + 1, right);
}

int binary_1(std::vector<int> &myV, int val, int left, int right) {
    if (left >= right) {
        return left;
    }
    int m = left + (right - left) / 2;
    if (myV[m] > val) {
        return binary_1(myV, val, left, m - 1);
    }
    return binary_1(myV, val, m + 1, right);
}

int binary_2(std::vector<int> &myV, int val, int left, int right) {
    if (left >= right) {
        return left;
    }
    int m = left + (right - left) / 2;
    if (myV[m] >= val) {
        return binary_2(myV, val, left, m - 1);
    }
    return binary_2(myV, val, m + 1, right);
}

int main() {
    std::ifstream fileIn("cautbin.in");
    std::ofstream fileOut("cautbin.out");

    int nV;
    fileIn >> nV;

    std::vector<int> myV;

    int aux;
    for (int i(0); i < nV; i++) {
        fileIn >> aux;
        myV.push_back(aux);
    }

    int a, b, c;

    fileIn >> c;

    for (int i(0); i < c; i++) {
        fileIn >> a >> b;
        if (a == 0) {
            fileOut << binary_0(myV, b, 0, nV - 1) << '\n';
        } else if (a == 1) {
            fileOut << binary_1(myV, b, 0, nV - 1) + 1 << '\n';
        } else {
            fileOut << binary_2(myV, b, 0, nV - 1) + 1 << '\n';
        }
    }

    fileIn.close();
    fileOut.close();
    return 0;
}