#include <stdio.h>

int v[100010];

int search1(int prim,int ultim,int key){
  int mij;
  while(prim<=ultim){
    mij=(prim+ultim)/2;
    if (v[mij]<=key) prim=mij+1;
    else ultim=mij-1;
  }
  mij=(prim+ultim)/2;
  if (v[mij]>key)mij--;
  if (v[mij]==key) return mij;
  return -1;
}

int search2(int prim, int ultim, int key){
  int mij;
  while(prim<ultim){
    mij=(prim+ultim)/2;
    if (v[mij]<=key) prim=mij+1;
    else ultim=mij;    
  }
  mij=(prim+ultim)/2;
  if(v[mij]>key) mij--;
  return mij;
}

int search3(int prim, int ultim, int key){
  int mij;
  while(prim<ultim){
    mij=(prim+ultim)/2;
    if (v[mij]<key) prim=mij+1;
    else ultim=mij;    
  }
  mij=(prim+ultim)/2;
  if(v[mij]<key) mij++;
  return mij;
}

int main()
{
  int i, n, m, tip, valoare;
  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", &tip, &valoare);
    if (tip == 0)
      printf("%d\n", search1(1,n,valoare));
    if (tip == 1)
      printf("%d\n", search2(1,n,valoare));
    if (tip == 2)
      printf("%d\n", search3(1,n,valoare));
  }  
  return 0;
}