#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");
long long v[500010];
int i,n,m,x,c;
int cautbin(long long v[100010],int n,int x)
{
	int l,r,mid;
	l=1;
	r=n;
	int i=0;
	while(l!=r)
	{
		mid=(l+r+1)/2;
		if(v[mid]==x)
		{
			while(v[mid]==x)
			{
				mid++;
			}
			return mid-1;
		}		
		else if(v[mid]>x)
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
		i++;
		if(i>n)
			return -1;
	}
}
int cautbin1(long long v[100010],int n,int x)
{
	int l,r,mid;
	l=1;
	r=n;
	int i=0;
	while(l!=r)
	{
		mid=(l+r+1)/2;
		if(v[mid]==x || (v[mid]<x&& v[mid+1]>x))
		{
			int ok=0;
			while(v[mid]==x)
			{
				mid++;
				ok=1;
			}
			if(ok)
				return mid-1;
			return mid;
		}		
		else if(v[mid]>x)
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
		i++;
		if(i>n)
			return -1;
	}
}

int cautbin2(long long v[100010],int n,int x)
{
	int l,r,mid;
	l=1;
	r=n;
	int i=0;
	while(l!=r)
	{
		mid=(l+r+1)/2;
		if(v[mid]==x || (v[mid]>x&& v[mid-1]<x))
		{
			int ok=0;
			while(v[mid]==x)
			{
				mid--;
				ok=1;
			}
			if(ok)
				return mid+1;
			return mid;
		}		
		else if(v[mid]>x)
		{
			r=mid-1;
		
		}
		else
		{
			l=mid+1;
		}
		i++;
		if(i>n)
			return -1;
	}
}

int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
	}
	fin>>m;
	for(i=1;i<=m;i++)
	{
		fin>>c;
		fin>>x;
		if(c==0)
		{
			fout<<cautbin(v,n,x)<<'\n';
		}
		if(c==1)
			fout<<cautbin1(v,n,x)<<'\n';
		if(c==2)
			fout<<cautbin2(v,n,x)<<'\n';
	}
	return 0;
}