//http://infoarena.ro/problema/cautbin
#include <cstdio>

using namespace std;

int n,a[100001],m;

void citire()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", &a[i]);
	scanf("%d", &m);
}

int caut(int val)
{
	int poz,i=0;
	for(poz=1; poz<n; poz<<=1);
	while(poz && a[i]!=val)
	{
		if(poz+i<=n && a[poz+i]<=val)
			i+=poz;
		poz>>=1;
	}
	return i;
}

int main()
{
	int caz, val;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	citire();
	while(m)
	{
		m--;
		scanf("%d%d", &caz, &val);
		int poz=caut(val);
		if(caz==0)
		{
			if(a[poz]!=val)
			{
				printf("-1\n");
				continue;
			}
			while(a[poz]==a[poz+1]) poz++;
			printf("%d\n", poz);
			continue;
		}
		if(caz==1)
		{
			while(a[poz]==a[poz+1]) poz++;
			printf("%d\n", poz);
			continue;
		}
		if(caz==2)
		{
			if(a[poz]!=val)
			{
				printf("%d\n", poz+1);
				continue;
			}
			while(a[poz]==a[poz-1]) poz--;
			printf("%d\n", poz);
			continue;
		}
	}
    return 0;
}