#include<iostream>
#include<fstream>
using namespace std;

int n, v[100002],m, intr, val;

int f0 ( int val, int st, int dr)
{
	int mijl;
	while(st<=dr)
	{
		mijl=(st+dr)/2;
		if(v[mijl]>val) dr=mijl-1;
			else st=mijl+1;
	}
	mijl=(st+dr)/2;
	if(v[mijl]>val) mijl--;
	if(v[mijl]==val) return mijl;
	return -1;	
}

int f1 (int val, int st, int dr)
{
	int mijl;
	while(st<dr)
	{
		mijl=(st+dr)/2;
		if(v[mijl]<=val)  st=mijl+1;
			else  dr=mijl;
	}
	mijl=(st+dr)/2;
	if(v[mijl]>val) mijl--;
	return mijl;
}

int f2 ( int val, int st, int dr)
{
	int mijl;
	while(st<dr)
	{
		mijl=(st+dr)/2;
		if(v[mijl]<val)  st=mijl+1;
			else  dr=mijl;
	}
	mijl=(st+dr)/2;
	if(v[mijl]<val) mijl++;	
	return mijl;	
}

int main()
{
	int i;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;	
	for(i=1;i<=m;i++)
	{
		f>>intr>>val;
		if ( intr==0) g<<f0(val,1,n)<<"\n";
			else 
				if( intr==1) g<<f1(val,1,n)<<"\n";
					else g<<f2(val,1,n)<<"\n";			
	}	
	return 0;
}