#include<bits/stdc++.h>
using namespace std;

const int N = 100009;
unsigned n, v[N];

ifstream in ("cautbin.in");
ofstream out("cautbin.out");
// auto& in = cin;
// auto& out = cout;
template <typename Predicate>
unsigned last_with_prop(Predicate predicate) {
    if(!predicate(v[0]))    return -1;
    unsigned poz=0;
	for(unsigned i=1<<31; i; i>>=1)
		if((poz+i) < n && predicate(v[poz+i]))
			poz+=i;
	return poz;
}

unsigned upper_bound(int x)
{
	//return upper_bound(v, v+n, x) - v;
	return 1 + last_with_prop([x](int n) { return n <= x; });
// 	unsigned poz=0;
// 	for(unsigned i=1<<31; i; i>>=1)
// 		if((poz+i) < n && v[poz+i] <= x)
// 			poz+=i;
// 	return poz+1;
}
unsigned lower_bound(int x)
{
	//return lower_bound(v, v+n, x) - v;
	return 1 + last_with_prop([x](int n) {return n < x; });
// 	unsigned poz=0;
// 	for(unsigned i=1<<31; i; i>>=1)
// 		if((poz+i) < n && v[poz+i] < x)
// 			poz+=i;
// 	if(v[poz] != x) poz++;
// 	return poz;
}
int main(){
	in>>n;
	for(unsigned i=0; i < n; i++)
		in>>v[i];
	
	int m, t, x, u, l;
	for(in>>m; m>0; m--)
	{
		in>>t>>x;
		u = upper_bound(x);
		if(t==0) out<<(v[u-1]==x?u:-1)<<endl;
		if(t==1) out<<lower_bound(x+1)<<endl;
		if(t==2) out<<lower_bound(x) + 1<<endl;
		
	}
	return 0;
}