#include <stdio.h>
int n,m;
int a[100005];
int cbin1 (int x)
{
    int in=1,sf=n,mij;
    while (in<=sf)
    {
        mij=in+sf/2;
        if (x<a[mij]) 
            sf=mij-1;
		else if (a[mij]<x) 
            in=mij+1;
        else
            return mij;
    }
    return -1;
}
int cbin2 (int x)
{
    int in=1,sf=n,mij,nr=0;
	while (in<=sf)
    {
        mij=in+sf/2;
		if (a[mij]<=x)
		{
            nr=mij;
            in=mij+1;
        }
		else 
            sf=mij-1;
	}
	return nr;
}
int cbin3 (int x)
{
    int in=1,sf=n,mij,nr=n+1;
	while (in<=sf)
    {
        mij=in+sf/2;
		if (a[mij]>=x)
		{
            nr=mij;
            sf=mij-1;
        }
		else 
            in=mij+1;
	}
	return nr;
}
int main()
{
    int i,t,x;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for (i=1; i<=m; ++i)
    {
          scanf("%d%d",&t,&x);
          if (t==0)
             printf("%d\n",cbin1 (x));
          else if (t==1)
             printf("%d\n",cbin2 (x));
          else 
             printf("%d\n",cbin3 (x));
    }          
    return 0;
}