#include <stdio.h>
#include <stdlib.h>
#define N 100005
int v[N];
int Cautare0(int st, int dr, int k){
  int mij;
  while(st<=dr){
    mij=(st+dr)/2;
    if(v[mij]<=k)
      st=mij+1;
    else
      dr=mij-1;
  }
  mij=(st+dr)/2;
  if(v[mij]>k)
    mij--;
  if(v[mij]==k)
    return mij;
  return -1;
}
int Cautare1(int st, int dr, int k){
  int mij;
  while(st<dr){
    mij=(st+dr)/2;
    if(v[mij]<=k)
      st=mij+1;
    else
      dr=mij;
  }
  mij=(st+dr)/2;
  if(v[mij]>k)
    mij--;
  return mij;
}
int Cautare2(int st, int dr, int k){
  int mij;
  while(st<dr){
    mij=(st+dr)/2;
    if(v[mij]<k)
      st=mij+1;
    else
      dr=mij;
  }
  mij=(st+dr)/2;
  if(v[mij]<k)
    mij++;
  return mij;
}
int main(){
  int i, n, m, op, nr;
  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, &nr);
    if(op==0)
      printf("%d\n", Cautare0(1, n, nr));
    if(op==1)
      printf("%d\n", Cautare1(1, n, nr));
    if(op==2)
      printf("%d\n", Cautare2(1, n, nr));
  }
  return 0;
}