#include<iostream.h>
#include<stdio.h>
 
long int n,numere[100001];
 
inline int BC1(long int x)
       {long int inceput=1,sfarsit=n,mediana;
        while(inceput<=sfarsit)
              {mediana=inceput+(sfarsit-inceput)/2;
               if(x<numere[mediana])
                      sfarsit=mediana-1;
               else if(x>numere[mediana])
                         inceput=mediana+1;
               else {mediana++;while(numere[mediana]==x) mediana++;
                     return mediana-1;}}
       return -1;}
inline int BC2(long int x)
      {long int lo,hi,mid,last=0;
       for(lo=1,hi=n;lo<=hi;)
	             {mid=lo+(hi-lo)/2;
		          if(numere[mid]<=x) last=mid,lo=mid+1;
		          else hi=mid-1;}
	   return last;}
inline int BC3(long int x)
    {long int lo,hi,mid,last=n+1;
     for(lo=1,hi=n;lo<=hi;)
	     {mid=lo+(hi-lo)/2;
          if (x<=numere[mid]) last=mid,hi=mid-1;
          else lo=mid+1;}
     return last;}
int main()
    {int i,t,x,tip;
    freopen("cautbin.in","r",stdin);freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
         scanf("%d",&numere[i]);
    scanf("%d",&t);
    for(i=1;i<=t;i++)
         {scanf("%d %d",&tip,&x);
         if(!tip)
                 printf("%d\n",BC1(x));
         else
             {if(tip==1)
                        printf("%d\n",BC2(x));
             else       printf("%d\n",BC3(x));}}
    return 0;}