#include <bits/stdc++.h>
#define NMax 100005
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n;
int A[NMax];

void binarySearch(int el, int tip) {
	int poz = -1;
	int left = 1;
	int right = n;
	while (left <= right) {
		int mij = (left+right)/2;
		if (tip == 0) {
			if (A[mij] == el)
				poz = mij;
			
			if (A[mij] > el)
				right = mij - 1;
			else
				left = mij + 1;
		} else if (tip == 1) {
			if (A[mij] > el) {
				right = mij - 1;
			} else {
				poz = mij;
				left = mij + 1;
			}
		} else if (tip == 2) {
			if (A[mij] < el) {
				left = mij + 1;
			} else {
				poz = mij;
				right = mij - 1;
			}
		}
	}
	
	g<<poz<<'\n';
}

void solve() {
	int m;
	f>>m;
	
	for (int i=1;i<=m;i++) {
		int tip, x;
		f>>tip>>x;
		binarySearch(x, tip);
	}
}

void read() {
	f>>n;
	for (int i=1;i<=n;i++)
		f>>A[i];
}

int main() {
	
	read();
	solve();
	
	f.close(); g.close();
	return 0;
}