#include<stdio.h>
#define Nmax 101000
int a[Nmax],n,m;

void citire()
{
}

int caut(int nr,int x)
{
 int p=1,u=n,mij;
 while(p<=u)
 {
	mij=(p+u)/2;
	if(a[mij]==x)
		break;
	if(a[mij]>x)
		u=mij-1;
	else
		p=mij+1;
 }
 switch(nr)
 {
	case 0: 	{if(a[mij]==x)
				{
				while(a[mij]==x && mij<=n)
					mij++;
				return mij-1;
				}
			else
				return -1;
			}
	case 1:	{if(a[mij]==x)
		 {	while(a[mij]==x)
				mij--;
			return mij+1;
		 }
		 else
			if(a[mij]<x)
				return mij;
			else
				return mij-1;
		 }
	case 2:{if(a[mij]==x)
		 {	while(a[mij]==x)
				mij++;
			return mij-1;
		 }
		 else
			if(a[mij]>x)
				return mij;
			else
				return mij+1;
		 }
 }
return 0;
}
int main()
{
 int x,nr;
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 scanf("%d",&n);
 int i;
 for(i=1;i<=n;i++)
	scanf("%d",&a[i]);
 scanf("%d",&m);
 for(i=1;i<=m;i++)
 {	scanf("%d%d",&nr,&x);
	printf("%d\n",caut(nr,x));
 }
 fclose(stdin);
 fclose(stdout);
 return 0;
}