#include<stdio.h>
#include<iostream.h>

#define MAX 100005

int n,m,v[MAX],op,x,var;

int i,j;

int binary_search(int val)
{
 int st=1,dr=n,m;

 while(st!=dr)
 {
   m=dr+(st-dr)/2;

   if(val>=v[m]) st=m;
   else        dr=m-1;  }

 return st;
}



int main()
{
  freopen("cautbin.in","r",stdin);
  freopen("cautbin.out","w",stdout);

  scanf("%d",&n);

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

  scanf("%d",&m);

  while(m--)
  {
  scanf("%d %d",&op,&x);

  var=binary_search(x);

  if(op==0 && v[var]!=x) printf("-1\n");
  if(op==0 && v[var]==x) printf("%d\n",var);

  if(op==1)  if(v[var]>x)   printf("%d\n",var-1);
	     else           printf("%d\n",var);

  if(op==2)  if(v[var]<x)   printf("%d\n",var+1);
	     else           printf("%d\n",var);
  }


  return 0;
}