#include <stdio.h>
#define dim 100001
using namespace std;
int n,m;   
int a[dim];   
int caut_bin1 (int x)   
{   
int inceput=1,sfarsit=n,mij;   
  while(inceput<=sfarsit)   
{mij=inceput+(sfarsit-inceput)/2;   
	if (x<a[mij])    
	 sfarsit=mij-1;   
	else if (a[mij]<x)    
	 inceput=mij+1;   
	else   
	return mij;   
    }   
    return -1;   
}   
int caut_bin2 (int x)   
{   
int inceput=1,sfarsit=n,mij,nr=0;   
 while(inceput<=sfarsit)   
    {mij=inceput+(sfarsit-inceput)/2;   
	if(a[mij]<=x)   
	{   
	nr=mij;   
	inceput=mij+1;   
	}   
	else    
	sfarsit=mij-1;   
    }   
    return nr;   
}   
int caut_bin3 (int x)   
{   
int inceput=1,sfarsit=n,mij,nr=n+1;   
    while (inceput<=sfarsit)   
    {mij=inceput+(sfarsit-inceput)/2;   
        if(a[mij]>=x)   
        { 
            nr=mij;   
            sfarsit=mij-1;   
        }   
        else    
            inceput=mij+1;   
    }   
    return nr;   
}   
int main()   
{int i,x;
short int t;
FILE *f=fopen("cautbin.in","r"), *g=fopen("cautbin.out","w");
       
    fscanf(f,"%d",&n);   
    for (i=1;i<=n;i++)   
        fscanf(f,"%d",&a[i]);   
    fscanf(f,"%d",&m);   
    for (i=1; i<=m; i++)   
    {   
          fscanf(f,"%hd%d",&t,&x);   
          if (t==0)   
             fprintf(g,"%d\n",caut_bin1 (x));   
          else if (t==1)   
             fprintf(g,"%d\n",caut_bin2 (x));   
          else    
             fprintf(g,"%d\n",caut_bin3 (x));   
    }             
fclose(f);
fclose(g);
return 0;   
}