#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long long int N,M,v[100005];

long long int cBin(int y) {
	long long int st = 1, dr = N, mij;
	while (st < dr) {
		mij = (st+dr)/2;
		if (y < v[mij])
			dr = mij;
		else
			st = mij + 1;
	}
	if (y == v[mij]) {
		int nr = v[mij];
		do {
			mij++;
		} while (v[mij] == nr);
		return mij - 1;
	}
	return -1;
}

long long int upBin(int y) {
	long long int st = 1, dr = N, mij;
	while (st < dr) {
		mij = (st + dr +1)/2;
		if (v[mij] <= y)
			st = mij;
		else
			dr = mij-1;
	}
	return dr;
}

long long int downBin(int y) {
	long long int st = 1, dr = N, mij;
	while (st < dr) {
		mij = (st+dr)/2;
		if (v[mij] < y)
			st = mij+1;
		else
			dr= mij;
	}
	return st;
}

int main()
{
	fin >> N;
	for (long long int i = 1; i <= N; i++)
		fin >> v[i];
	fin >> M;
	for (long long int i = 1; i <= M; i++) {
		long long int x, y;
		fin >> x >> y;
		if (x == 0)
			fout << cBin(y);
		else if (x == 1)
			fout << upBin(y);
		else
			fout << downBin(y);
		fout << endl;
	}
}