#include<stdio.h>
int a[100006];
int n,m;
int stop;
int tmp;
void caut0(int x,int i,int j)
{if(i<=j)
  {
   if(i==j)
   {
	   if(a[i]==x)
   {
	   if(i>tmp)
       { tmp=i;}
   }	   
   }else{
	int med=(i+j)/2;
	if(a[med]==x) 
		if(med>tmp)
       { tmp=med;}
	if(x<a[med])
	{caut0(x,i,med);
	}
	else
	{caut0(x,med+1,j);
	}
   }
  }
}
void caut1(int x,int i,int j)
{if(i<=j)
  {
   if(i==j)
   {if(a[i]<=x)
	   if(i>tmp)
        tmp=i;		   
   }else{
	int med=(i+j)/2;
	if(a[med]<=x) 
		if(med>tmp)
       { tmp=med;}
	   
	if(x<a[med])
	{caut1(x,i,med);
	}
	else
	{caut1(x,med+1,j);
	}
   }
  }
}
void caut2(int x,int i,int j)
{if(i<=j)
  {
   if(i==j)
   {if(a[i]>=x)
	   if(i<tmp)
        tmp=i;		   
   }else{
	int med=(i+j)/2;
	if(a[med]>=x) 
		if(med<tmp)
       { tmp=med;}
	if(x<a[med])
	{caut2(x,i,med);
	}
	else
	{caut2(x,med+1,j);
	}
   }
  }
}
int main()
{freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 int i,x,y;
 scanf("%d ",&n);
 for(i=1;i<=n;i++)
 {
  scanf("%d ",&a[i]);
 }  
 scanf("%d ",&m);
 for(i=0;i<m;i++)
 { stop=0;
   tmp=0;
   scanf("%d %d",&x,&y);
   if(x==0)
   {caut0(y,1,n);
   
    if(tmp==0)
	 printf("-1 \n");	
    else
		printf("%d \n",tmp);
   }
   if(x==1)
   {caut1(y,1,n);
    printf("%d \n",tmp);
   }
   if(x==2)
   {tmp=n+1;
	caut2(y,1,n);
    printf("%d \n",tmp);
   }
 }
 
 
return 0;
}