#include<stdio.h>
int cautare_binara_0(int v[],int st,int dr,int x)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij+1;
          else dr=mij-1;
    }
    mij=(st+dr)/2;
    if(v[mij]>x)
        mij--;
    if(v[mij]==x)
        return mij;
    return -1;
}
int cautare_binara_1(int v[],int st,int dr,int x)
{
    int mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij+1;
            else dr=mij;
    }
    mij=(st+dr)/2;
    if(v[mij]>x)
        mij--;
    return mij;
}
int cautare_binara_2(int v[],int st,int dr,int x)
{
    int mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij+1;
            else dr=mij;
    }
    mij=(st+dr)/2;
    if(v[mij]<x)
        mij++;
    return mij;
}
int main()
{
    int i,v[100010],n,m,tip,x;
    FILE *f=fopen("cautbin.in","rt");
    FILE *g=fopen("cautbin.out","wt");
    fscanf(f,"%i",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%i",&v[i]);
    fscanf(f,"%i",&m);
    for(int j=1;j<=m;j++)
    {
        fscanf(f,"%i%i",&tip,&x);
        if(tip==0)
            fprintf(g,"%i\n",cautare_binara_0(v,1,n,x));
        if(tip==1)
            fprintf(g,"%i\n",cautare_binara_1(v,1,n,x));
        if(tip==2)
            fprintf(g,"%i\n",cautare_binara_2(v,1,n,x));
    }
    fclose(f);
    fclose(g);
    return 0;
}