#include<stdio.h>
#define nmax 100001
int v[nmax];
int i,n,m,x;

int binar0(int v[], int n, int x)
	{
	int l,r,m;
	l=1,r=n; //stabilim capetele vectorului
	while(l<=r) //cat timp putem cauta in vector
		{
		m=(l+r)/2; //mislocul portiunii v[l] - v[r]
		if(v[m]==x) return m; //am gasit elementul, deci returnam pozitia
		if(v[m]>x) r=m-1; //elementul gasit la pozitia m este mai mare dacat x, deci restrictionam cautarea in prima jumatate
		else l=m+1; //elementul gasit la pozitia m este mai mic decat x, deci restrictionam cautarea in a 2-a jumatate
		}
	return -1; //nu a fost gasit elementul
	}

int binar1(int v[], int n, int x)
	{
	int l,r,m,poz=-1;
	l=1,r=n; //stabilim capetele vectorului
	while(l<=r)
		{
		m=(l+r)/2; //mislocul portiunii v[i] - v[r]
		if(v[m]<=x) //mm gasit un numar mai mic sau egal decat x
			{
			poz=m; //salvam pozitia lui
			l=m+1; //cautam in continuare in partea dreapta un numar mai mare decat v[m] si mai mic sau egal decat x
			}
		else r=m-1; //numarul este mai mare, deci cautam in partea stanga
		}
	return poz;
	}

int binar2(int v[], int n, int x)
	{
	int l,r,m,poz=-1;
	l=1,r=n; //stabilim capetele vectorului
	while(l<=r)
		{
		m=(l+r)/2; //mislocul portiunii v[i] - v[r]
		if(v[m]>=x) //am gasit un numar mai mare sau egal cu x
			{
			poz=m; //salvam pozitia lui
			r=m-1; //cautam in continuare in partea stanga un numar mai mic decat v[m] si mai mare sau egal decat x
			}
		else l=m+1; //numarul este mai mic, deci cautam in partea dreapta
		}
	return poz;
	}
	
int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);

scanf("%d",&n);
for(i=1;i<=n;scanf("%d ",&v[i++]));

scanf("%d",&m);

while(m--)
  {
  scanf("%d %d",&i,&x);
  if(!i) printf("%d\n",binar0(v,n,x));
  else if(i==1) printf("%d\n",binar1(v,n,x));
  else if(i==2) printf("%d\n",binar2(v,n,x));
  }
return 0;
}