#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
vector<int>a;
int c,x,st,dr,mij;
int sch()
{
	while(st!=dr)
	{
		mij=st+((dr-st)>>1);
		if(x<=a[mij])
			dr=mij;
		else
			st=mij+1;
	}
	return mij;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	int n,m,i,j;
	scanf("%d",&n);
	a.push_back(1);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&j);
		a.push_back(j);
	}
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d%d",&c,&x);
		st=1;dr=a.size()-1;
		sch();
		if(c==0)
			if(x!=a[st])
				printf("-1\n");
			else
				printf("%d\n",st);
		if(c==1)
			if(a[st]>x) 
				printf("%d\n",st-1);
			else
				printf("%d\n",st);
		if(c==2)
			if(a[st]<x)
				printf("%d\n",st+1);
			else
				printf("%d\n",st);
	}
	return 0;
}