#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>

using namespace std;

int n, m, t, op;

int upperBound(vector<int> &v, int val) {
	int start = 0, end = v.size() - 1;

	while (start <= end) {
		int m = (end - start) / 2 + start;

		if (start == end && v[start] == val)
			return start;
		if (m > 0 && v[m - 1] == val && v[m] != val)
			return m - 1;
		if (m < end && v[m] == val && v[m + 1] != val)
			return m;
		if (v[m] > val)
			end = m - 1;
		else if (v[m] < val)
			start = m + 1;
		else start ++;
	}

	return -1;
}

int upperBound2(vector<int> &v, int val) {
	int start = 0, end = v.size() - 1;

	while (start <= end) {
		int m = (end - start) / 2 + start;

		if (start == end && v[start] <= val)
			return start;
		if (m > 0 && v[m - 1] <= val && v[m] > val)
			return m - 1;
		if (m < end && v[m] <= val && v[m + 1] > val)
			return m;
		if (v[m] > val)
			end = m - 1;
		else if (v[m] < val)
			start = m + 1;
		else start ++;
	}

	return -1;
}

int lowerBound(vector<int> &v, int val) {
	int start = 0, end = v.size() - 1;

	while (start <= end) {
		int m = (end - start) / 2 + start;

		if (start == end && v[start] >= val)
			return start;
		if (m > 0 && v[m] >= val && v[m - 1] < val)
			return m;
		if (m < end && v[m] < val && v[m + 1] >= val)
			return m + 1;
		if (v[m] > val)
			end = m - 1;
		else if (v[m] < val)
			start = m + 1;
		else end --;
	}

	return -1;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);

    vector<int> v;
    for (int i = 0; i < n; i ++) {
    		scanf("%d", &t);
    		v.push_back(t);
    }

    scanf("%d", &m);
    for (int i = 0; i < m; i ++) {
    	scanf("%d %d", &op, &t);
    	if (op == 0) {
    		int sol = upperBound(v, t);
    		printf("%d\n", sol + 1);
    	} else if (op == 1) {
    		int sol = upperBound2(v, t);
    		printf("%d\n", sol + 1);
    	} else if (op == 2) {
    		int sol = lowerBound(v, t);
    		printf("%d\n", sol + 1);
    	}

    }

    return 0;
}