#include <fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long n,m,v[100005],i,x,y;

void cauta(int x,int y, int st,int dr)
{
	int gasit=0,m;
	while(!gasit && st<=dr)
	{ m=(st+dr)/2;
	  if(v[m]==y)
		if(x<=1) { while(m<=n &&v[m]==y)m++;
				g<< m-1<<'\n'; gasit=1;
		         }
		else { while(m && v[m]==y)m--;
				g<< m+1<<'\n';gasit=1;
		        }
	    else		
			if(v[m]>y)dr=m-1;
			else st=m+1;
	}
   if(!gasit)
   switch(x){ 
			case 0: g<<"-1\n"; break;
			case 1: g<<dr<<'\n';break;
			case 2: g<<st<<'\n';break;
		    }
}

int main()
{
	
	f>>n;
	for(i=1;i<=n;i++)
		{ f>>v[i];}
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		cauta(x,y,1,n);
	}
	f.close();
	g.close();
	return 0;
}