#include <stdio.h>
#include <cstdio>
#define RRR ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long

#define pp pair<int,int>
using namespace std;
int ar[100001];
int n,low,high,mid;

int bina(int x)
{
	 low = 1;
	 high = n;
	
	
	while (low < high)
	{
		
		 mid = low + high >> 1;
		if (ar[mid] > x)
			high = mid - 1;
		else
		{
			
			low = mid + 1;
		}
	}
	mid = low + high >> 1;
	if (ar[mid] == x)
		printf("%d\n",mid);
	else if (ar[mid-1] == x)
		printf("%d\n",mid-1);
	else printf("%d\n",-1);
	return 0;
}

int binar(int x)
{
	 low = 1;
	 high = n;
	
	while (low < high)
	{
		mid = low + high >> 1;
		if (ar[mid] > x)
			high = mid;
		else low = mid + 1;
	}
	mid = low + high >> 1;
	if (ar[mid] > x)
		mid--;
	printf("%d\n",mid);
	return 0;
}

int binar2(int x)
{
	 low = 1;
	 high = n;
	 
	while (low < high)
	{
		mid = low + high >> 1;
		if (ar[mid] < x)
			low = mid+1;
		else high = mid;
	}
	mid = low + high >> 1;
	if (ar[mid] < x)
		mid++;
	printf("%d\n",mid);
	return 0;
}

int main()
{
	
//										freopen("text.txt","r",stdin);
		int i,j,q,a,x;
		freopen("cautbin.in","r",stdin);
		freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for ( i=1;i<=n;i++)
	{
		
		scanf("%d",&ar[i]);
	}
	//cout << bina(3);
	
	scanf("%d",&q);
	for ( i=0;i<q;i++)
	{
		
		scanf("%d%d",&a,&x);
		if (a == 0)
		{
			bina(x);
		}
		else if (a == 1)
		{
			binar(x);
			
		}
		else if (a == 2)
		{
			binar2(x);
		}

	}
	return 0;
 
}