#include <stdio.h>


int a[100005],poz;

 int n,m,i,intr,val;
 int cb0(int x) {
    int mij,hi=n,lo=1,poz=-1;
    while (lo<=hi) {
    mij=(lo+hi)/2;
    if (a[mij]==x)
          {poz=mij;
          lo=mij+1;
          }
          else
          if (a[mij]<x) lo=mij+1;
          else hi=mij-1;}
     return poz;
    }
int cb1(int x) {
    int mij,poz,hi=n,lo=1; ;
    while (lo<=hi) {
          mij=(hi+lo)/2;
          if (a[mij]<=x) {
                         poz=mij;
                         lo=mij+1;
                         }
          else
          hi=mij-1;}
     return poz;
}
int cb2 (int x) {
     int mij,poz, lo=1,hi=n ;
    while (lo<=hi) {
          mij=(hi+lo)/2;
          if (a[mij]>=x) { poz=mij;
                           hi=mij-1;
                           }
               else                       
           lo=mij+1;
           }
     return poz;
}    
         
int main() {
    FILE* f=fopen("cautbin.in", "r");
    FILE* g=fopen("cautbin.out", "w+");
    fscanf(f,"%d", &n);
    for (i=1;i<=n;i++)
        fscanf (f, "%d ", &a[i]);
    fscanf(f,"%d", &m);
    for (i=1;i<=m;i++){
          fscanf (f,"%d %d", &intr, &val);
          if (intr==0) 
              fprintf(g,"%d\n", cb0(val));
           if (intr==1)
              fprintf(g,"%d\n",cb1(val));
          if (intr==2)
              fprintf(g,"%d\n", cb2(val));
              }
    fclose(f);
    fclose(g);
return 0;
}