#include <cstdio>

using namespace std;
int n,m,op,x,a[100001];
int bs_0(int x, int left, int right)
{
   while(left < right)
   {
       int m = (left+right)/2;
       if(a[m]<=x) left = m+1;
       else right = m;
   }
   m = (left+right)/2;
   if(a[m]>x) m--;
   if (a[m]== x)
   return m;

   return -1;

}
int bs_1(int x, int left, int right)
{
   while(left < right)
   {
       int m = (left+right)/2;
       if(a[m]<=x) left = m+1;
       else right = m;
   }
   m = (left+right)/2;
   if(a[m]>x)
    return m-1;
   return m;
}

int bs_2(int x, int left, int right)
{
   while(left < right)
   {
       int m = (left+right)/2;
       if(a[m]<x) left = m+1;
       else right = m;
   }
   m = (left+right)/2;
   if(a[m]<x)
    return m+1;
   return m;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for( int i=1;i <=n; ++i )
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for( int i=1; i<=m;++i)
     {
    scanf("%d %d",&op,&x);
    if(op == 0)
    {
        printf("%d\n",bs_0(x,1,n));
    }
    else if (op==1) printf("%d\n",bs_1(x,1,n));
    else if (op==2) printf("%d",bs_2(x,1,n));
     }
    return 0;
}