#include <algorithm>
#define DIM 100003

using namespace std ;

int n , m ;
int v[DIM] ;
int a , b ;
int st , dr ,mij ;
int key ;

int binary_search1(int x) {
      int in=1,sf=n,mij;
    while (in<=sf)
    {
        mij=in+(sf-in)/2;
        if (x<v[mij])
            sf=mij-1;
        else if (v[mij]<x)
            in=mij+1;
        else
            return mij;
    }
    return -1;
}
int binary_search2(int x) {
  dr=n ;
  key=-1 ;
  st=1 ;
  while (st<=dr) {
    mij=st+(dr-st)/2 ;
    if (v[mij]<=x) {
      key=mij;
      st=mij+1;
    }
    if (v[mij]>x)
      dr=mij-1;
  }
  return key ;
}
int binary_search3(int x) {
  dr=x ;
  key=n+1 ;
  st=1 ;
  while (st<=dr) {
    mij=st+(dr-st)/2 ;
    if (v[mij]>=x) {
      key=mij;
      dr=mij-1;
    }
    if(v[mij]<x) {
      st=mij+1;
    }
  }
  return key;
}

int main() {
  freopen ("cautbin.in","r",stdin) ;
  freopen ("cautbin.out","w",stdout) ;
  
  scanf ("%d" , &n) ;
  for (int i=1 ; i<=n ; ++i) {
    scanf ("%d" , &v[i]);
  }
  scanf ("%d" , &m ) ;
  for (int i=1 ; i<=m ; ++i) {
    scanf ("%d%d" , &a , &b) ;
    if (a==0) {
      printf ("%d\n",binary_search1(b));
    }
    if (a==1) {
      printf ("%d\n",binary_search2(b));
    }
    if (a==2) {
      printf ("%d\n",binary_search3(b));
    }
  }

  return 0;
}