#include <algorithm>
#define DIM 100000

using namespace std ;

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

int binary_search1(int x) {
  dr=n ;
  key=-1 ;
  st=1 ;
  while (st<dr) {
    mij=(st+dr)/2 ;
    if (v[mij]==x) {
      st=mij+1 ;
      if (key<mij) {
        key=mij ;
      }
    }
    if (v[mij]<x) {
      dr=mij-1 ;
    }
    if (v[mij]>x) {
      st=mij+1 ;
    }
  }
  return key ;
}
int binary_search2(int x) {
  dr=n ;
  key=-1 ;
  st=1 ;
  while (st<=dr) {
    mij=(st+dr)/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)/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;
}