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

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

int main()
{
	fin >> N;
	for (int i = 1; i <= N; i++)
		fin >> v[i];
	fin >> M;
	for (int i = 1; i <= M; i++) {
		int x, y;
		fin >> x >> y;
		fout << cautareBinara(x, y)<<endl;
	}
}