#include<cstdio>
#include<iostream>
using namespace std;
int n,m,a[100010];
int main()
{
	int i,poz,x,y;
	freopen("cautbin.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);
	freopen("cautbin.out","w",stdout);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		if(x==0)
		{
			poz=upper_bound(a+1,a+n+1,y)-a;
			if(a[poz-1]==y)
				printf("%d\n",poz-1);
			else
				printf("-1\n");
		}
		else
			if(x==1)
			{
				poz=upper_bound(a+1,a+n+1,y)-a;
				poz--;
				printf("%d\n",poz);
			}
			else
			{
				poz=lower_bound(a+1,a+n+1,y)-a;
				if(a[poz]!=y)
					poz++;
				printf("%d\n",poz);
			}
	}
	return 0;
}