//cautare binara cu STL: lower_bound si upper_bound 9.01.2012
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int nmax=100001;
int n,v[nmax],m;

int main ()
{
	int tip,x;
	ifstream fin ("cautbin.in");
	ofstream fout("cautbin.out");
	
	fin>>n;
	for (int i=1;i<=n;++i)
		fin>>v[i];
	
	fin>>m;
	for (int i=1;i<=m;++i)
	{
		fin>>tip>>x;
		if (tip==0)	
		{
			int lb=lower_bound(v+1,v+n+1,x+1)-v;
			if (v[lb-1] == x) fout<<lb-1<<'\n'; 
			else fout<<-1<<'\n';
		}
		else if (tip==1) 
		{
			int lb=lower_bound(v+1,v+n+1,x+1)-v;
			fout<<lb-1<<'\n';
		}
		else if (tip==2) 
		{
			int ub=upper_bound(v+1,v+n+1,x-1)-v;
			fout<<ub<<'\n';
		}
		//else cout<<"n-avem/n";
	}
	
	fin.close();
	fout.close();
	return 0;
}