#include <iostream>
#include <stdio.h>

using namespace std;

int m, n, v[100005];

int bsearch0 (int x) {
	int mid, l = 0, r = n;
	
	while (l < r) {
		mid = (l + r) / 2;
		
		if (v[mid] == x) {
			break;
		} else if (x < v[mid]) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	if (v[mid] == x) {
		while (v[mid+1] == x) {
			++mid;
		}
		return mid;
	}
	
	return -1;
}

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

int bsearch2 (int x) {
	int mid, l = 0, r = n;
	
	while (l < r) {
		mid = (l + r) / 2;
		
		if (v[mid] >= x) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	return mid;
}
	
int main (void) {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int x, c;
		cin >> c >> x;
		
		if (c == 0) {
			cout << bsearch0(x) + 1 << '\n';
		} else if (c == 1) {
			cout << bsearch1(x) << '\n';
		} else {
			cout << bsearch2(x) + 2 << '\n';
		}
	}
	
	return 0;
}