#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;
unsigned upper_bound(int x)
{
	return upper_bound(v, v+n, x) - v;
	unsigned poz=0;
	for(unsigned i=1<<31; i; i>>=1)
		if((poz+i) < n && v[poz+i] <= x)
		{
			// out<<"i: "<<i<<endl;
			// out<<"poz|i: "<<(poz|i)<<endl;
			poz+=i;	
		}
	return poz;
}
unsigned lower_bound(int x)
{
	return lower_bound(v, v+n, x) - v;
	unsigned poz=0;
	for(unsigned i=1<<31; i; i>>=1)
		if((poz+i) < n && v[poz+i] < x)
		{
			// out<<"i: "<<i<<endl;
			// out<<"poz+i: "<<(poz+i)<<endl;
			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;
		// out<<"x:"<<x<<endl;
		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;
}