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

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