#include <bits/stdc++.h>
using namespace std;
int hi,lo,x,mid,a[10000000],m,n,k;
int cautbin0(){
lo=1;
hi=n;
while (lo<=hi){
	mid=lo+(hi-lo)/2;
	if (a[mid]<=x) lo=mid+1;
	  else hi=mid-1;
}
if (a[hi]==x) return hi;
    else return -1;
}

int cautbin1(){
	lo=1;
	hi=n;
while (lo<=hi){
	mid=lo+(hi-lo)/2;
	  if (a[mid]<=x) lo=mid+1;
	     else hi=mid-1;
}
return hi;
}
int cautbin2(){
	lo=1;
	hi=n;
	while (lo<=hi){
		mid=lo+(hi-lo)/2;
		if (a[mid]>=x) hi=mid-1;
		  else lo=mid+1;
	}
	return lo;
}
int main(){
	ifstream cin("cautbin.in");
	ofstream cout("cautbin.out");
	cin>>n;
	for (int i=1;i<=n;i++)
	cin>>a[i];
	cin>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>k>>x;
		if (k==0) cout<<cautbin0()<<'\n';
        if (k==1) cout<<cautbin1()<<'\n';
        if (k==2) cout<<cautbin2()<<'\n';
	}
	
	return 0;
}