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

int v[100001];

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

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

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

int main() {
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	int n, m, question_type, current_value;
	fin >> n;
	for (int i = 1; i <= n; i++) {
		fin >> v[i];
	}
	fin >> m;
	for (int i = 1; i <= m; i++) {
		fin >> question_type >> current_value;
		if (question_type == 0) {
			fout << binary_search_0(1, n, current_value) << '\n';
		} else if (question_type == 1) {
			fout << binary_search_1(1, n, current_value) << '\n';
		} else {
			fout << binary_search_2(1, n, current_value) << '\n';
		}
	}
	return 0;
}