#include<stdio.h>

int a[100001],i,k,x,lo,hi,mid,m,n,ok;

int main()
{ freopen("cautbin.in","r",stdin);
  freopen("cautbin.out","w",stdout);
  
  scanf("%d",&n);
  for(i=1;i<=n;i++) scanf("%d",&a[i]);
  scanf("%d",&m);
  
  for(i=1;i<=m;i++) { scanf("%d %d",&k,&x);
                      lo=1;
                      hi=n;
                      ok=0;
                      while(lo<hi&&!ok)
                              { mid=lo+(hi-lo)/2;
                                if(a[mid]==x)ok=1;
                                else if(x>a[mid]) lo=mid+1;
                                else hi=mid-1;  
                              }
                      if(k==0) { if(ok) { lo=mid;
                                          while(a[lo]==x)lo++;                                          
                                          printf("%d\n",lo-1);
                                        }     
                                 else printf("-1\n");
                                 
                               }  
                      if(k==1) { if(a[mid]>x) printf("%d\n",mid-1);
                                                           
                                 else printf("%d\n",mid);
                               }  
                      if(k==2) { if(a[mid]<x) printf("%d\n",mid+1);
                                 else printf("%d\n",mid);
                               }             
                    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}