#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <iomanip>
#include <cmath>

#define e '\n'

using namespace std;

#define FILE "cautbin"

#define INF 1023456789
#define ll long long

#ifdef FILE
	ifstream f(string (string(FILE) + ".in").c_str());
	ofstream g(string (string(FILE) + ".out").c_str());
#endif
#ifndef FILE
	#define f cin
	#define g cout
#endif

int i, j, n, m, x, y;
vector <int> v;

#define NMOD 1999999973


int main() {

	f >> n;
	for (i=1; i<=n; i++) {
		f >> x;
		v.push_back(x);
	}

	f>> m;
	for (i=1; i<=m; i++) {
		f >> x >> y;
		if (x==0) {
			if (binary_search(v.begin(), v.end(), y)) {
				int xx = upper_bound(v.begin(), v.end(), y) - v.begin();
				g << xx << e;
			} else {
				g << -1 << e;
			}
		} else if (x==1) {
			int xx = upper_bound(v.begin(), v.end(), y) - v.begin();
			g << xx << e;
		} else if (x==2) {
			int xx = lower_bound(v.begin(), v.end(), y) - v.begin() + 1;
			g << xx << e;
		}
	}

}