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

int v[100001];

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

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

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

int main() {
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	int n, m, i, question_type, current_value;
	fin >> n;
	for (i = 1; i <= n; i++) {
		fin >> v[i];
	}
	fin >> m;
	for (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;
}