#include <fstream>
using namespace std;

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

int v[100001];

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

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

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


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;
}