/*
		Keep It Simple!
*/

#include<stdio.h>

#define MaxN 100001


int N,Seq[MaxN],T;

int FirstBinSearch(int value)
{
	int left = 1, right = N;
	while( left<right-1 )
	{
	     int mid = (left + right)/2;
	     if(Seq[right] == value)
					 return right;
	     if(Seq[mid] <= value)
	         left = mid;
	     else
					 right  = mid - 1;
	}
  if( Seq[right] == value )
			return right;
	else if(Seq[left] == value)
			return left;
	else
			return -1;
}

int SecondBinSearch(int value)
{
   int left = 1,right = N;

   while(left < right-1)
   {
			int mid = (left+right)/2;
			if(Seq[right] <= value)
				return right;
			if(Seq[mid] > value)
				right = mid-1;
			else
			  left = mid;
   }

  if( Seq[right] <= value )
			return right;
	else if(Seq[left] <= value)
			return left;
	else
			return -1;
}

int LastBinSearch(int value)
{
   int left = 1,right = N;

   while(left < right-1)
   {
			int mid = (left+right)/2;
			if(Seq[left] >= value)
				return left;
			if(Seq[mid] < value)
				left = mid+1;
			else
			  right = mid;
   }

  if( Seq[left] >= value )
			return left;
	else if(Seq[right] >= value)
			return right;
	else
			return -1;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);

	scanf("%d",&N);

	for(int i=1; i<=N; i++)
		scanf("%d",&Seq[i]);

	scanf("%d",&T);

	int type,val;

	while(T--)
	{
		scanf("%d%d",&type,&val);

		if(type == 0)
		    printf("%d\n",FirstBinSearch(val));
		else if(type == 1)
		    printf("%d\n",SecondBinSearch(val));
		else if(type == 2)
				printf("%d\n",LastBinSearch(val));
	}
}