#include <iostream>
#include <fstream>
using namespace std;

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

const int MAX_SIZE = 100000;
int v[MAX_SIZE + 1], n, m, tip_of_question, number_searched;

int binary_search(int number_searched) {
    int left = 1, right = n;
    while (left < right) {
        int middle = (left + right) / 2;
        if (number_searched <= v[middle]) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    if (tip_of_question < 2) {
        while(v[left] <= number_searched) {
            ++left;
        }
        if (v[left - 1] == number_searched && tip_of_question == 0) {
            return left - 1;
        } else if (tip_of_question == 1) {
            return left - 1;
        }
        return -1;
    }
    return left;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    fin >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> tip_of_question >> number_searched;
        if (tip_of_question == 0) {
            fout << binary_search(number_searched) << '\n';
        } else if (tip_of_question == 1) {
            fout << binary_search(number_searched) << '\n';
        } else {
            fout << binary_search(number_searched) << '\n';
        }
    }
}