#include<iostream>
#include<fstream>
using namespace std; 
long int n, x[100001], val1, m;
long int caut_bin(long int x[],long int st,long int dr,long int val,int cond)
{
	if(st==dr)
		{
		if(x[st]==val)
			return st;
		if(cond==0)
			return -1;
		if(cond==1)
			return st-1;
		if(cond==2)
			return st+1;
		}
	else
		{
		long int mij;
		mij=st+(dr-st)/2;
		if(val==x[mij])
			return mij;
		if(val>x[mij])
			caut_bin(x,mij,dr,val,cond);
		else
			caut_bin(x,st,mij,val,cond);
		}
		

}

int main(){
	ifstream f1("cautbin.in");
	f1>>n;
	for(long int i=1; i<=n; i++)
		f1>>x[i];
	int poz;
	f1>>m;
	ofstream f2("cautbin.out");
	for(long int i=1; i<=m; i++)
		{long int cond1;
		f1>>cond1;
		f1>>val1;
		poz=caut_bin(x,1,n,val1,cond1);
		
		if(cond1==0)
			{if(poz!=-1)
			{long int j;
			for(j=poz; j<=n; j++)
				if(x[j]!=x[poz])
					break;
			f2<<j-1<<endl;
			}
			else
				f2<<poz;}
		else
			if(cond1==2)
				{
				if(val1==x[poz])
					{long int j=poz;
					while(x[j]==x[poz])
						j--;
					f2<<j+1<<endl;
					}
				else
					return poz;
				}
			else
				if(cond1==1)
					if(val1==x[poz])
						{long int j=poz;
						while(x[j]==x[poz])
							j++;
						f2<<j-1<<endl;
						}
				else
					return poz;
				

		}
	f1.close();	
	f2.close();
}