#include <cstdio>
using namespace std;

FILE *in; FILE *out;
long n,m,a[100010],i,x,y;

void caut1 (long l,long r,long y) {
     long u=l,v=r,z;
     while (u<v) {
           z=(u+v+1)/2;
           if (a[z]<=y) u=z; else v=z-1;
     }
     if (u==v) fprintf (out,"%ld\n",u+1); else fprintf (out,"-1\n");;
}

void caut2 (long l,long r,long y) {
     long u=l,v=r,z;
     while (u<v) {
           z=(u+v+1)/2;
           if (a[z]<=y) u=z; else v=z-1;
     }
     fprintf (out,"%ld\n",u+1);
}

void caut3 (long l,long r,long y) {
     long u=l,v=r,z;
     while (u<v) {
           z=(u+v)/2;
           if (a[z]>=y) v=z; else u=z+1;
     }
     fprintf (out,"%ld\n",u+1);
}

int main () {
    in=fopen ("cautbin.in","r"); out=fopen ("cautbin.out","w");
    fscanf (in,"%ld",&n);
    for (i=0; i<n; i++) fscanf (in,"%ld",&a[i]);
    fscanf (in,"%ld",&m);
    for (i=0; i<m; i++) {
        fscanf (in,"%ld%ld",&x,&y);
        if (x==0) caut1 (0,n-1,y); else
           if (x==1) caut2 (0,n-1,y); else
              caut3 (0,n-1,y);
    }
    fclose (in); fclose (out);
    return 0;
}