// Craciun Catalin
//  Infoarena
//   Cautbin

#include <iostream>
#include <fstream>
#include <map>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cstring>
#include <cassert>
#include <ctime>
#include <cstdlib>

#define NMax 100005

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

#define DBG 1

int A[NMax];
int n,m;

int cautBin(int type, int x) {
	
	if (type == 0) {
		
		int left = 1, right = n;
		int poz = -1;
		
		while (left <= right) {
			int mij = (left+right)/2;
			
			if (A[mij] == x) {
				poz = mij;
				while (A[poz] == x && poz <= n)
					poz++;
				poz--; 
				
				return poz;
			} else if (A[mij] > x) {
				right = mij - 1;
			} else {
				left = mij + 1;
			}
		}
		
		return poz;
	} else if (type == 1) {
		int left = 1, right = n;
		int poz = -1;
		
		while (left <= right) {
			int mij = (left + right)/2;
			
			if (A[mij] > x) {
				right = mij - 1;
			} else if (A[mij] == x) {
				poz = mij;
				while (A[poz] == x && poz <= n)
					poz++;
				poz--;
				
				return poz;
			} else if (A[mij] < x) {
				poz = mij;
				left = mij + 1;
			}
		}
		
		return poz;
	} else if (type == 2) {
		int left = 1, right = n;
		int poz = -1;
		
		while (left <= right) {
			int mij = (left + right)/2;
			
			if (A[mij] < x) {
				left = mij + 1;
			} else if (A[mij] == x) {
				poz = mij;
				while (A[poz] == x && poz >= 1)
					poz--;
				poz++;
				
				return poz;
			} else if (A[mij] > x) {
				poz = mij;
				right = mij - 1;
			}
		}
		
		return poz;
	}
	
	return -1;
}

void read() {
	
	f>>n;
	for (int i=1; i<=n; i++) {
		f>>A[i];
	}
	f>>m;
	for (int i=1;i<=m;i++) {
		int t, x;
		f>>t>>x;
		g<<cautBin(t,x)<<'\n';
	}
	
	f.close();
}

int main() {

#ifdef DBG
	float one = clock();
#endif

	read();
	
#ifdef DBG
	cout<<fixed<<setprecision(8)<<(clock()-one)/CLOCKS_PER_SEC;
#endif

	return 0;
}