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

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int n;
vector<int> v;
int m;
int intrebare, x;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		int nr; cin >> nr;
		v.push_back(nr);
	}
	cin >> m;
	for(int i = 1; i <= m; i ++) {
		cin >> intrebare >> x;
		if(intrebare == 0) {
			int indice_dr = -1;
			int st = 0, dr = n-1;
			while (st <= dr) {
				int mij = (st+dr)/2;
				if(v[mij] == x) {
					indice_dr = mij;
					st = mij + 1;
				}
				else {
					dr = mij - 1;
				}
			}
			cout << indice_dr+1 << '\n';
		}
		else if (intrebare == 1) {
			int indice_st = -1;
			int st = 0, dr = n-1;
			while (st <= dr) {
				int mij = (st+dr)/2;
				if(v[mij] <= x) {
					indice_st = mij;
					st = mij + 1;
				}
				else {
					dr = mij - 1;
				}
			}
			cout << indice_st+1 << '\n';
		}
		else {
			int indice = -1;
			int st = 0, dr = n-1;
			while (st <= dr) {
				int mij = (st+dr)/2;
				if(v[mij] >= x) {
					indice = mij;
					dr = mij - 1;
				}
				else {
					st = mij + 1;
				}
			}
			cout << indice+1 << '\n';
		}
	}
}