#include <cstdio>

using namespace std;

#define Nmax 101000
#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;
   mij=(p+u)>>1;
   while(p<=u)
   {
	   if (v[mij]==x) return mij;
	   if (v[mij]<x)
	   {
		  p=mij+1;
          mij=(p+u)>>1;
	   }
	   else
	   {
		   u=mij-1;
		   mij=(p+u)>>1;
	   }
   }
   if (v[mij]!=0) 
	    return -1;
   return mij;
}

inline int bs1(int x)
{
   int mij,p,u;
   p=1;
   u=n;
   mij=(p+u)>>1;
   while(p<u)
   {
	   
	   if (v[mij]<x)
	   {
		  p=mij+1;
          mij=(p+u)>>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;
   mij=(p+u)>>1;
   while(p<u)
   {
	   
	   if (v[mij]<x)
	   {
		  p=mij+1;
          mij=(p+u)>>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;
}