#include <stdio.h>
int n,m,v[100001],i,j,p,x,o;
int cautbin(int s,int d)
{ 
  int m;
  while(s<d)
  {
   m=(s+d)/2;
   if(x<v[m])
    d=m;
   else
   if(x>v[m])
   s=m+1;
   else
   if(x==v[m])
    return m;
   }
   p=s;
   return -1;
} 
    
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);
    for(i=1;i<=m;i++)
    {
                     scanf("%d %d",&o,&x);
                     if(o==0)
                      printf("%d\n",cautbin(1,n));
                     if(o==1) 
                      if(cautbin(1,n)==-1)
                       printf("%d\n",p-1);
                      else
                      printf("%d\n",cautbin(1,n));
                     if(o==2) 
                      if(cautbin(1,n)==-1)
                       printf("%d\n",p);
                      else
                      printf("%d\n",cautbin(1,n));
                     
    }
    return 0;
}