#include <fstream>
#include <iostream>
#include <vector>
#define MAX_SIZE 100000

using namespace std;

int v[MAX_SIZE + 1], n, m;

int binarySearch(int elem) {
    int left, right, mid, idx;
    left = 0;
    right = n - 1;
    idx = -1;

    while (left <= right) {
        mid = left + (right - left) / 2;

        if (v[mid] == elem) {
            idx = mid;
            left = mid + 1;
        }
        else if (elem < v[mid])
            right = mid - 1;
        else 
            left = mid + 1;
    }

    if (idx != -1)
        return idx + 1;

    return idx;
}

int binarySearch1(int elem) {
    int left, right, mid, idx;
    left = 0;
    right = n - 1;
    idx = -1;

    while (left <= right) {
        mid = left + (right - left) / 2;
        if (v[mid] <= elem) {
            idx = mid;
            left = mid + 1;
        }

        else 
            right = mid - 1;
    }

    if (idx != -1)
        return idx + 1;

    return idx;
}

int binarySearch2(int elem) {
    int left, right, mid, idx;
    left = 0;
    right = n - 1;
    idx = -1;

    while (left <= right) {
        mid = left + (right - left) / 2;
        if (v[mid] >= elem) {
            idx = mid;
            right = mid - 1;
        }

        else 
            left = mid + 1;
    }

    if (idx != -1)
        return idx + 1;

    return idx;
}

int main() {
    int op, x;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    fin >> n;

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

    fin >> m;

    for (int i = 0; i < m; ++i) {
        fin >> op >> x;
        if (op == 0) {
            fout << binarySearch(x) << "\n";
        }
        else if (op == 1) {
            fout << binarySearch1(x) << "\n";
        }
        else 
            fout << binarySearch2(x) << "\n";
    }

    return 0;
}