#include <stdio.h>
FILE *f,*g; int x,a[100000],n;
int cautare0(int st,int dr)
{
    int mij;
    if (dr-st>=0){
    mij=(st+dr)/2;
    if (a[mij]==x&&a[mij+1]>x) return mij;
    if (a[mij]==x&&a[mij+1]==x) return cautare0(mij+1,dr);
    if (x<a[mij]) return (cautare0(st,mij-1));
    if (a[mij]<x) return (cautare0(mij+1,dr));
    }
    else return -1;
}
int cautare1(int st,int dr)
{
    int mij;
    if (dr-st>=0){
    mij=(st+dr)/2;
    if (dr==n) if (a[dr<=x]) return dr;
    if (a[mij]<=x&&a[mij+1]>x) return mij;
    if (a[mij]<=x&&a[mij+1]<=x) return cautare1(mij+1,dr);
    if (x<a[mij]) return cautare1(st,mij-1);
    }
}
int cautare2(int st,int dr)
{
    int mij;
    if (dr-st>=0){
    mij=(st+dr)/2;
    if (st==1) if (a[st>=x]) return st;
    if (a[mij]>=x&&a[mij-1]<x) return mij;
    if (a[mij]>=x&&a[mij-1]>=x) return cautare2(st,mij-1);
    if (x>a[mij]) return cautare2(mij+1,dr);
    }
}
int main()
{
    int i,c,m;
    f=fopen("cautbin.in","r");
    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",&c,&x);
        if (c==0) fprintf(g,"%d\n",cautare0(1,n));
        else if (c==1) fprintf(g,"%d\n",cautare1(1,n));
        else fprintf(g,"%d\n",cautare2(1,n));
    }
    fclose(f);
    fclose(g);
    return 0;
}