#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("cautbin.in");
ofstream g("cautbin.out");
int n;
int cautareBinara2(int v[100001], int x) {
	int st = 1, dr = n;
    while (st < dr) {
        int mij = st + (dr - st) / 2;
        if(v[mij] < x)
            st = mij + 1;
        else dr = mij;

    }
    return st;
}
int cautareBinara1(int v[100001], int x, int op) {
	int st = 1, dr = n, gasit = 0, poz;
	while(st <= dr) {
        int mij = st + (dr - st) / 2;
		if(v[mij] <= x) {
            st = mij + 1;
            poz = mij;
            if(v[mij] == x)
                gasit = 1;
		}
		else dr = mij - 1;
	}
	if(v[st] == x) {
        poz = st;
        gasit = 1;
	}
	else if (v[st] < x && op == 1)
		poz = st;
	if(gasit || op == 1)
        return poz;
    else return -1;
}
int main() {

	f >> n;
	int v[100001];
	for(int i = 1; i <= n; i++)
		f >> v[i];
	int m;
	f >> m;
	while(m--) {
		int operatie, x;
		f >> operatie >> x;
		if(operatie == 0)
			g << cautareBinara1(v,x, operatie) << endl;
		else if (operatie == 1)
			g << cautareBinara1(v,x, operatie) << endl;
		else g << cautareBinara2(v,x) << endl;
	}
	f.close();
	g.close();
	return 0;
}