#include <bits/stdc++.h>

using namespace std;

int get_low(vector<int> v, int l, int r, int x) 
{	
	int pos_left = -1;

	while (l <= r) {
		int mid = l + (r - l) / 2;
		
		if (v[mid] >= x) {  
			pos_left = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return pos_left;	
}

int get_high(vector<int> v, int l, int r, int x)
{
	int pos_right = -1;
		
	while (l <= r) {
		int mid = l + (r - l) / 2;
		
		if (v[mid] <= x) {
			pos_right = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return pos_right;
} 


int option0(vector<int> v, int l, int r, int x) 
{
	return (get_high(v, l, r, x) == -1) ? -1 : (get_high(v, l, r, x) + 1);
}

int option1(vector <int> v, int l, int r, int x) 
{
	return get_high(v, l, r, x) + 1;
}

int option2(vector<int> v, int l, int r, int x) 
{
	return get_low(v, l, r, x) + 1;
}

int main()
{
	freopen ("cautbin.in", "r", stdin);
	freopen ("cautbin.out", "w", stdout);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	
	int m;
	cin >> m;
	int type, x;
	for (int i = 0; i < m; ++i) {
		cin >> type >> x; 
		if (type == 0) 
			cout << option0(v, 0, n - 1, x) << "\n";
		if (type == 1) 
			cout << option1(v, 0, n - 1, x) << "\n";
		if (type == 2) 
			cout << option2(v, 0, n - 1, x) << "\n";
	}

	return 0;
}