#include <bits/stdc++.h>
#define newline "\n"
using namespace std;
ifstream fin("cautbin.in");
ofstream fout ("cautbin.out");

int v[100001], n, m, x, t;
int maxBinaryPos(int v[100001], int nr);
int minBinaryPos(int v[100001], int nr);
int main() {
	fin >> n;
	for(int i = 1; i <= n; ++i)
	    fin >> v[i];
	fin >> m;
	for(int i = 1; i <= m; ++i) {
	    fin >> x >> t;
	    if(x == 0 || x == 1)
	       fout << maxBinaryPos(v, t) << newline;
	    if(x == 2)
	       fout << minBinaryPos(v, t) << newline; 
	}
}
int maxBinaryPos(int v[100001], int nr) {
	int lf = 1, rg = n, mid;
	while(lf < rg) {
		 mid = (lf + rg) / 2;
		 if(v[mid] == t) {
		    if(v[mid + 1] == t) {
		      lf = mid + 1;
		    } else {
		    	return mid;
		    }
		 } else if (v[mid] > t) {
		 	 rg = mid;
		 } else {
		 	 lf = mid + 1;
		 }
	}
	if(x == 0)
	   return -1;
}
int minBinaryPos(int v[100001], int nr) {
	int lf = 1, rg = n, mid;
	while(lf < rg) {
		 mid = (lf + rg) / 2;
		 if(v[mid] == t) {
		    if(v[mid - 1] == t) {
		      rg = mid;
		    } else {
		    	return mid;
		    }
		 } else if(v[mid] > t) {
		 	 rg = mid;
		 } else {
		 	lf = mid + 1;
		 }
	}
}