#include <cstdio>
#include <algorithm>
using namespace std;

int i,x,n,m,q,a[100010];
int cb0(int l,int r)
{
     int m ;
     while(l<=r)
     {
          m=(l+r)/2;
          if (a[m]<=x) l=m+1;
          else r=m-1;
     }
     m=(l+r)/2;
     if (a[m]>x)
         m=m-1;
     if (a[m]==x)
        return m; else return -1;
 }
int cb1(int l,int r)
{
     int m;
     while(l<r)
     {
          m=(l+r)/2;
          if (a[m]<=x)
          l=m+1;
          else
          r=m;
     }
    m=(l+r)/2;
    if (a[m]>x)
    m--;
    return m;
}

int cb2(int l,int r)
{
     int m;
     while(l<r)
     {
         m=(l+r)/2;
         if (a[m]<x)
         l=m+1;
         else
         r=m;
     }
     m=(l+r)/2;
     if (a[m]<x)
     m++;
    return m;
}
int main()
    {
        freopen("cautbin.in","r",stdin);
        freopen("cautbin.out","w",stdout);
        scanf("%d",&n);
        for (i=1 ;i<=n ;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        scanf("%d",&m);
        for (i=1 ;i<=m ;i++)
             {
                 scanf("%d%d",&q,&x);
                 if (q==0) printf("%d\n",cb0(1,n));
                 if (q==1) printf("%d\n",cb1(1,n));
                 if (q==2) printf("%d\n",cb2(1,n));
             }
     }