#include <stdio.h>  
int l[100000];  
      
int cauta0(int li, int ls, int x);  
int cauta1(int li, int ls, int x);
int cauta2(int li, int ls, int x);        
      
int main()  
{  
  int i, n, m, t, x;  
  freopen("cautbin.in", "r", stdin);  
  freopen("cautbin.out", "w", stdout);  
  scanf("%d", &n);  
  for (i=1; i<=n; i++)  
    scanf("%d", &l[i]);  
  scanf("%d", &m);  
  for (i=0; i<m; i++)  
  {
	  scanf("%d%d", &t, &x);
	  if (t==0)
		  printf("%d\n", cauta0(1, n, x));
	  if (t==1)
		  printf("%d\n", cauta1(1, n, x));
	  if (t==2)
		  printf("%d\n", cauta2(1, n, x));
  }//for i
  return 0;  
}//main

int cauta0(int li, int ls, int x)  
{  
	int m;
	while (li<ls)
	{ 
	  	m=(li+ls)/2;
 		if (x>=l[m])  
  			li=m+1;  
 		else  
  			ls=m;  
	}//while  
	m=(li+ls)/2;
   if (x<l[m])
		m--;
	if (l[m]==x)
	  return m;  
	else 
	  return -1;
}//cauta0


int cauta1(int li, int ls, int x)  
{  
	int m;
	while (li<ls)
	{ 
	  	m=(li+ls)/2;
 		if (x>=l[m])  
  			li=m+1;  
 		else  
  			ls=m;  
	}//while  
	m=(li+ls)/2;
   if (x<l[m])
		m--;
	return m;  
}//cauta1

int cauta2(int li, int ls, int x)  
{  
	int m;
	while (li<ls)
	{ 
	  	m=(li+ls)/2;
 		if (x>l[m])  
  			li=m+1;  
 		else  
  			ls=m;  
	}//while  
	m=(li+ls)/2;
   if (x>l[m])
		m++;
	return m;  
}//cauta2