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

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

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

int f0 ( int val, int i)
{
	if(i==0) return -1;
	do
	{
	i++;
	}while(v[i+1]==val);
	return i;
}

int f1 (int val, int i)
{
	if (f0(val,i)>=i) return f0(val,i);
	else
	do
	{
		i--;
	}while(v[i]==val);
	return i;
}

int f2 ( int val, int i)
{
	if(v[i-1]==val)
	{
	while(v[i-1]==val)
	{
		i--;
	}
	return i;
	} 
	else return i;	
		
}

int main()
{
	int i,indice;
	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;
		indice=cautare(v,val,1,n);
		if ( intr==0) g<<f0(val,indice)<<endl;
		else if( intr==1) g<<f1(val,indice)<<endl;
		else g<<f2(val,indice)<<endl;			
	}	

	return 0;
}