#include<stdio.h>

long n,m,op,x,i,v[100001];

long calc_solutie(long op, long x)
{

long st=1;
long dr=n;
while(st<=dr)
{
long mid=st+(dr-st)/2;
if (v[mid]>x) dr=mid-1;
else if (v[mid]<x) st=mid+1;
else return mid;
	}

switch(op)
{
case 0: return -1;
case 1: return st-1;
case 2: return st;
}
return 0;			}



int main()
{

freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);

	scanf("%li",&n);

for(i=1;i<=n;scanf("%li",&v[i++]));

	scanf("%li",&m);

for(i=1;i<=m;i++){
	scanf("%li %li",&op,&x);
	printf("%li \n",calc_solutie(op,x));
      }

fclose(stdin);
fclose(stdout);
	return 0;
	}