#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 st, fi, mid;
    for (st = 1,fi = n;st <= fi; )
    {
        mid = st + (fi-st) / 2;
        if (nr < vec[mid]) fi = mid-1;
        else if (vec[mid] < nr) st = mid+1;
        else return mid;
    }
    return -1;
}

int cauta1 (int nr)
{
    int st, fi, mid, last = 0;
    for (st = 1, fi = n; st <= fi; )
    {
        mid = st + (fi-st) / 2;
        if (vec[mid] <= nr) last = mid, st = mid+1;
        else fi = mid-1;
    }
    return last;
}

int cauta2 (int nr)
{
  int st, fi, mid, last = n+1;

    for (st = 1, fi = n; st <= fi; )
    {
        mid = st + (fi-st) / 2;
        if (nr <= vec[mid]) last = mid, fi = mid-1;
        else st = mid+1;
    }
    return last;
}