#include <cstdio>

using namespace std;

#define Nmax 101010
#define FIN "cautbin.in"
#define FOUT "cautbin.out"

int v[Nmax];
int tip,x;
int n,m;

inline int bs0(int x)
{
   int mij,p,u;
   p=1;   
   u=n;   
   while (p<=u)   
   {   
       mij=(p+u)>>1;   
       if (v[mij]==x) return mij;   
       if (v[mij]<x)   
           {   
                p=mij+1;   
           }   
           else  
           {   
                u=mij-1;   
           }   
   }   
    if (v[mij]!=0) return -1;   
     return mij; 
}

inline int bs1(int x)
{
   int mij,p,u;
   p=1;   
   u=n;   
   while (p<u)   
   {   
        mij=(p+u)>>1;   
        if (v[mij]<x)   
            {   
                p=mij+1;   
            }   
            else  
            {   
                u=mij;   
            }   
   }   
    mij=(p+u)>>1;   
    if (v[mij]>x) mij--;   
    return mij;  
}

inline int bs2(int x)
{
   int mij,p,u;
   p=1;   
   u=n;   
   while (p<u)   
   {   
        mij=(p+u)>>1;   
        if (v[mij]<x)    
            {   
                p=mij+1;   
            }   
            else  
            {   
                u=mij;   
            }   
   }   
    mij=(p+u)>>1;   
    if (v[mij]<x) mij++;   
    return mij;   

}
	
void citire()
{
	int i,j;
	
	freopen(FIN,"r",stdin);
	freopen(FOUT,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
		 scanf("%d", &v[i]);
	scanf("%d", &m);
	while(m--)
	{
		scanf("%d %d", &tip, &x);
		if (tip==0)
		{
			printf("%d\n", bs0(x));
		}
		else
		if (tip==1)
		{
		    printf("%d\n", bs1(x));
		}
		else
		{
			printf("%d\n", bs2(x));
		}
	}
}

int main()
{
	citire();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}