#include<stdio.h>
using namespace std;
FILE *f1=fopen("cautbin.in","r");
FILE *f2=fopen("cautbin.out","w");
int n,v[100001],m,i,a,x;
int cautB0(int st,int dr){
    int mij;
    if (st==dr && v[st]==x) return st;
    if (st>dr) return -1;
    mij=st+(dr-st)/2;
    if (x<v[mij]) return cautB0(st,mij-1);
      else
        if (x>v[mij]) return cautB0(mij+1,dr);
    if (x==v[mij] && v[mij+1]==x) return cautB0(mij+1,dr);
      else
        if (x==v[mij] && v[mij+1]!=x) return mij;
}
int cautB1(int st,int dr){
    int mij;
    mij=st+(dr-st)/2;
    if (st==dr && v[st]<=x) return st;
    if (st>dr) return -1;
    if (v[mij]==x && v[mij+1]==x) return cautB1(mij+1,dr);
    if (v[mij]<=x && v[mij+1]>x) return mij;
    if (v[mij]>x) return cautB1(st,mij-1);
      else
        return cautB1(mij,dr);
}
int cautB2(int st,int dr){
     int mij;
     mij=st+(dr-st)/2;
     if (st==dr && v[st]>=x) return st;
     if (st>dr) return -1;
     if (v[mij]>=x && v[mij-1]<x) return mij;
     if (v[mij]<x) return cautB2(mij+1,dr);
       else
        return cautB2(st,mij);
}
int main(){
    fscanf(f1,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf(f1,"%d",&v[i]);
    fscanf(f1,"%d",&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f1,"%d%d",&a,&x);
        if (a==0) fprintf(f2,"%d\n",cautB0(1,n));
        if (a==1) fprintf(f2,"%d\n",cautB1(1,n));
        if (a==2) fprintf(f2,"%d\n",cautB2(1,n));
    }
    fclose(f1);
    fclose(f2);
    return 0;
}