//// cautbin.cpp : Defines the entry point for the console application.
////
//
//#include <iostream>
//#include <fstream>
//#define MAXN 10005
//#define MAX(a,b) ( (a) > (b) ? (a) : (b))
//
//using namespace std;
//
//ifstream in("cautbin.in");
//ofstream out("cautbin.out");
//
//int N, M, v[MAXN],mid,st,dr,a,nr;
//
////void cit() {
////	in >> N;
////	for (int i = 1; i <= N; i++) {
////		in >> v[i];
////	}
////
////}
////int cautbin_0(int nr) {
////	int mid, st = 1, dr = N;
////	while (st <= dr) {
////
////		mid = (st + dr) / 2;
////		if (v[mid] > nr) {
////			dr = mid - 1;
////		}
////		else if (v[mid] <= nr) {
////			st = mid + 1;
////		}
////	}
////	mid = (st + dr) / 2;
////	if (v[dr] == nr) {
////		return dr;
////	}
////	else {
////		return -1;
////	}
////}
////int cautbin_1(int nr) {
////	int mid, st = 1, dr = N;
////	while (st <= dr) {
////
////		mid = (st + dr) / 2;
////		if (v[mid] > nr) {
////			dr = mid - 1;
////		}
////		else if (v[mid] <= nr) {
////			st = mid  + 1;
////		}
////	}
////	mid = (st + dr) / 2;
////	return dr;
////	
////}
////int cautbin_2(int nr) {
////	int mid, st = 1, dr = N;
////	while (st <= dr) {
////
////		mid = (st + dr) / 2;
////		if (v[mid] >= nr) {
////			dr = mid - 1;
////		}
////		else if (v[mid] < nr) {
////			st = mid + 1;
////		}
////	}
////	mid = (st + dr) / 2;
////	return st;
////}
//
//int main()
//{
//	in >> N;
//	for (int i = 1; i <= N; i++) {
//		in >> v[i];
//	}
//	in >> M;
//	for (int i = 1; i <= M; i++) {
//		
//		in >> a >> nr;
//		if (a == 0) {
//			st = 1, dr = N;
//			while (st <= dr) {
//
//				mid = (st + dr) / 2;
//				if (v[mid] > nr) {
//					dr = mid - 1;
//				}
//				else if (v[mid] <= nr) {
//					st = mid + 1;
//				}
//			}
//			if (v[dr] == nr) {
//				out<< dr <<"\n";
//			}
//			else {
//				out<<-1<<"\n";
//			}
//		}
//		else if (a == 1) {
//			st = 1, dr = N;
//			while (st <= dr) {
//
//				mid = (st + dr) / 2;
//				if (v[mid] > nr) {
//					dr = mid - 1;
//				}
//				else if (v[mid] <= nr) {
//					st = mid + 1;
//				}
//			}
//			out<< dr<<"\n";
//		}
//		else if(a == 2) {
//			st = 1, dr = N;
//			while (st <= dr) {
//
//				mid = (st + dr) / 2;
//				if (v[mid] >= nr) {
//					dr = mid - 1;
//				}
//				else if (v[mid] < nr) {
//					st = mid + 1;
//				}
//			}
//			out<< st<<"\n";
//		}
//	}
//	return 0;
//}
//
#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, i, v[100001], t, x, st, dr, m, mid;
int main()
{
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> v[i];
	fin >> m;
	for (i = 1; i <= m; i++) {
		fin >> t >> x;
		if (t == 0) {
			st = 1; dr = n;
			while (st <= dr) {
				mid = (st + dr) / 2;
				if (v[mid] <= x)
					st = mid + 1;
				else
					dr = mid - 1;
			}
			if (v[dr] == x)
				fout << dr << "\n";
			else
				fout << "-1" << "\n";
		}
		if (t == 1) {
			st = 1; dr = n;
			while (st <= dr) {
				mid = (st + dr) / 2;
				if (v[mid] <= x)
					st = mid + 1;
				else dr = mid - 1;
			}
			fout << dr << "\n";
		}

		if (t == 2) {
			st = 1; dr = n;
			while (st <= dr) {
				mid = (st + dr) / 2;
				if (v[mid] >= x)
					dr = mid - 1;
				else st = mid + 1;
			}
			fout << st << "\n";

		}
	}
	return 0;
}