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



/*0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta 
valoare nu se gaseste in sir*/

/*1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x 
in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x*/

/*2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu 
x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x*/



void cauta(int x,int y, int st,int dr)
{
	//int  mij = st + (dr-st)/2;
	
	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];
//	g<<v[i]<<' ';
		}
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		//  g<<"\n **** "<<x<<" caut "<<y<<"\n";
		
			cauta(x,y,1,n);
	}
	f.close();
	g.close();
	return 0;
}