#include <cstdio>
int st,dr,mij,a[100001],n,m,x,i,nr,poz;
int cautbin (int nr, int st, int dr)
{
	int mij;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (a[mij]==nr) return mij;
		if (a[mij]>nr) dr=mij+1;
		else
		if (a[mij]<nr) st=mij;
	}
return -1;
}
int main ()
{
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",&x,&nr);
		if (x==0)
		{
		  poz=cautbin(nr,1,n);
		  if (poz==-1) printf("-1\n");
		  else
		  {
			  while (a[poz]==nr) ++poz;
		      printf("%d\n",poz-1);
		  }			  
		}
		else
		if (x==1)
		{
           st=1;dr=n;
            while(st<=dr) 
			{
               mij=(dr+st)/2;
			   if (a[mij]<=x & poz<mij)  {poz=mij;st=mij+1;}
                  else
               if (a[mij]<=x) st=mij+1;
                  else
               if (a[mij]>x) dr=mij-1;
			}
           if (poz==0) printf("-1\n");
              else printf("%d\n",poz-1);
		}
		else
		if (x==2)
		{
			poz=n+1;
            st=1;dr=n;
            while(st<=dr) 
			{
             mij=(dr+st)/2;
			 if (a[mij]>=x & poz>mij)  {poz=mij; dr=mij-1;}
			     else
             if (a[mij]>=x) dr=mij-1;
				 else
			 if (a[mij]<x) st=mij+1;
			}
              if (poz==0) printf("-1\n");
                 else printf("%d\n",poz);
		}
	}
return 0;
}