#include <stdio.h>
#define NMAX 100001
 
int N,M,x;
int A[NMAX];


int caut0(int s,int d)
{
	if (s>d) return -1;
int m=(s+d)/2;


if(x==A[m]) 	{
					while(A[m]==A[m+1]) 
					{
						m++;
					}
				return m;
				}


if(x<A[m]) return caut0(s,m-1);
	else return caut0(m+1,d);	
	
}

int caut1(int s,int d)
{
	if (s>d) 	{int m=(s+d)/2;
				return m;	
				}

	
	
int m=(s+d)/2;


if(x==A[m]) 	{
					while(A[m]==A[m+1]) 
					{
						m++;
					}
				return m;
				}


if(x<A[m]) return caut1(s,m-1);
	else return caut1(m+1,d);	




}

int caut2(int s,int d)
{
	if (s>d) 	{int m=(s+d)/2;
				return m;	
				}

	
	
int m=(s+d)/2;


if(x==A[m]) 	{
					while(A[m]==A[m-1]) 
					{
						m--;
					}
				return m;
				}


if(x<A[m]) return caut1(s,m-1);
	else return caut1(m+1,d);	



	
}



void f()
{

int i,j;

	FILE *fout=fopen("cautbin.out","w");
	FILE *fin=fopen("cautbin.in","r");
	fscanf(fin,"%d",&N);
	
	for(int i=1;i<=N;i++)
		fscanf(fin,"%d",&A[i]);
	
	fscanf(fin,"%d",&M);
	
	
for(i=1;i<=M;i++)
	{	fscanf(fin,"%d %d",&j,&x);
		if (j==0) fprintf(fout,"%d\n",caut0(1,N));
		if (j==1) fprintf(fout,"%d\n",caut1(1,N));
		if (j==2) fprintf(fout,"%d\n",caut2(1,N));
	
	}
}	


int main()
{
	f();
return 0;
}