#include <fstream>
using namespace std;

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

int v[100001];

int binarySearch0(int left, int right, int value) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (v[mid] <= value) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if (v[left - 1] == value) {
        return left - 1;
    }
    return -1;
}

int binarySearch1(int left, int right, int value) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (v[mid] <= value) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left - 1;
}

int binarySearch2(int left, int right, int value) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (v[mid] < value) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}


int main() {
    int N, M, value, question;
    fin >> N;
    for (int i = 1; i <= N; ++i) {
        fin >> v[i];
    }
    fin >> M;
    for (int i = 1; i <= M; ++i) {
        fin >> question >> value;
        if (question == 0) {
            fout << binarySearch0(1, N + 1, value) << '\n';
        } else if (question == 1) {
            fout << binarySearch1(1, N + 1, value) << '\n';
        } else {
            fout << binarySearch2(1, N, value) << '\n';
        }
    }
    return 0;
}