#include <cstdio>
using namespace std;

FILE* fin=fopen("cautbin.in","r");
FILE* fout=fopen("cautbin.out","w");
int vec[100005];

int cauta0 (int nr) ;
int cauta1 (int nr);
int cauta2 (int nr);
int n;
int main ()
{
    int i,m,q,x;
    fscanf(fin,"%d", &n);
    for (i=1; i<=n; i++)
        fscanf(fin,"%d", &vec[i]);
    fscanf(fin,"%d", &m);
    for(i=1;i<=m;i++)
    {
          fscanf(fin,"%d %d",&q, &x);
          if(q==1)
             fprintf(fout,"%d\n",cauta0(x));
          if (q==1)
             fprintf(fout,"%d\n",cauta1(x));
          if (q==2)
             fprintf(fout,"%d\n",cauta2(x));
    }
    return 0;
}

int cauta0 (int nr)
{
    int m,st,fi;
    st=1; fi=n;
    while (fi-st>1)
    {
        m=(st+fi)/2;
        if (vec[m] <= nr)
            st=m+1;
        else
            fi=m-1;
    }
    m=(st + fi) / 2;

    if (vec[m]>nr) m --;
    if (vec[m]==nr)
        return m;
    return -1;
}

int cauta1 (int nr)
{
    int m, st,fi;
    st=1; fi=n;
    while (fi-st>1)
    {
        m=(st + fi) / 2;
        if (vec[m]<=nr)
            st=m + 1;
        else
            fi=m;
    }

    m=(st+fi)/2;
    if (vec[m]>nr)
       -- m;
    return m;
}

int cauta2 (int nr)
{
    int m,st,fi;
    st=1; fi=n;
    while (fi-st>1)
    {
        m=(st+fi)/2;
        if (vec[m]<nr)
            st=m+1;
        else
            fi=m;
    }

    m=(st+fi)/2;
    if (vec[m]<nr)
       ++ m;
    return m;
}