#include<stdio.h>
long f[100001],a[100001],b[100001];
int main()
{
	long n,m,i,p=0,val=0,j;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
	  scanf("%ld",&f[i]);
	scanf("%ld",&m);
	for(i=1;i<=m;i++)
	  scanf("%ld%ld",&a[i],&b[i]);
	for(i=1;i<=m;i++)
	  {
	  val=0;
	  p=0;
	  if(a[i]==0)
		      {
			for(j=n;j>=n/2;j--)
			  if(f[j]<=b[i])
			      {
				printf("%ld\n",j);
				val=1;
				p=1;
				break;
			      }
			if(val==0)
			 {
			  for(j=n/2+1;j>=1;j--)
			    if(f[j]<=b[i])
				{
				   printf("%ld\n",j);
				   p=1;
				   break;
				}
			 }
		       if(p==0)
			  printf("-1\n");
		      }
	  else
	      if(a[i]==1)
			  {
			    for(j=n;j>=n/2;j--)
			     if(f[j]<=b[i])
			      {
				printf("%ld\n",j);
				val=1;
				break;
			      }
			    if(val==0)
			      {
				  for(j=n/2+1;j>=1;j--)
				    if(f[j]<=b[i])
					   {
					   printf("%ld\n",j);
					   break;
					   }
			      }
			  }
	      else
		  if(a[i]==2)
			     {
			     for(j=1;j<=n/2;j++)
			       if(f[j]>=b[i])
				   {
				      printf("%ld\n");
				      val=1;
				      p=1;
				      break;
				   }
			     if(val==0)
				{
				   for(j=n/2;j<=n;j++)
				     if(f[j]>=b[i])
					  {
					  printf("%ld\n",j);
					  break;
					  }
				}
			     }
	  }
	return 0;
}