#include <stdio.h>
#include <stdlib.h>
#define N_MAX 100000

int v[N_MAX],x,n;

int c1() {
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(v[mij]==x) {
              poz=mij;
              st=mij+1;
        }
        else if(v[mij]<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return poz;
}


int c2() {
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(v[mij]<=x) {
              poz=mij;
              st=mij+1;
        }
        else
            dr=mij-1;
    }
    return poz;
}


int c3() {
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(v[mij]>=x) {
              poz=mij;
              dr=mij-1;
        }
        else
            st=mij+1;
    }
    return poz;
}


int main()
{
    FILE *fin=fopen("cautbin.in","r");
    FILE *fout=fopen("cautbin.out","w");
    int m,i,r;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&v[i]);
    fscanf(fin,"%d",&m);
    for(i=0;i<m;i++) {
        fscanf(fin,"%d%d",&r,&x);
        if(r==0) r=c1();
        else if(r==1) r=c2();
        else r=c3();
        fprintf(fout,"%d\n",r);
    }


    return 0;
}