#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<fstream>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>
using namespace std;

#define DMAX 500001

FILE *f, *g;

int n, m, q, nr;
vector<int> v;

int BinSearch  (int x, int st, int dr){
	int mij = st + (dr - st) / 2;

	if (st > dr) {
		switch (q) {
		case 0: return -1;
		case 1: return dr;
		case 2: return st;
		default: break;
		}
	}
	else{
		if (v[mij] == x){
			switch (q){
			case 0: 
			case 1: 
				while (mij < n && v[mij] == x)	mij++;
				return mij - 1;
			case 2: 
				while (mij >= 0 && v[mij] == x)	mij--;
				return mij + 1;
			default: break;
			}
		}
		else if (v[mij] > x)	return BinSearch(x, st, mij - 1);
		else					return BinSearch(x, mij + 1, dr);
	}

	return -2;
}

int main(){
	int i, x;

	f = freopen("test.in", "r", stdin);
	g = freopen("test.out", "w", stdout);

	scanf("%d", &n);
	for (i = 0; i < n; i++) { scanf("%d", &x); v.push_back(x); }

	scanf("%d", &m);
	for (i = 0; i < m; i++){
		scanf ("%d %d", &q, &nr);
		x = BinSearch(nr, 0, n - 1);
		printf("%d\n", x == -1 ? x : x + 1);
	}

	return 0;
}