#include<fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int x,n,i,t,tip,a[100001];

int cautbin0(int x,int st,int dr)
{
	int m=(st+dr)/2;
	
	if (st>dr) return -1;
	if (a[m]==x) 
	{
		while (a[m+1]==a[m]) m++;
		return m;
	}
	
	if (a[m]>x) return cautbin0(x,st,m-1);
		else return cautbin0(x,m+1,dr);
}

int cautbin1(int x,int st,int dr)
{
	int m=(st+dr)/2;
	
	if (st==dr) 
	{
		while (a[m]>x) m--;
		while (a[m+1]<=x) m++;
		return m;
	}
	
	if (a[m]>x) return cautbin1(x,st,m-1);
		else return cautbin1(x,m+1,dr);
}


int cautbin2(int x,int st,int dr)
{
	int m=(st+dr)/2;
	
	if (st==dr) 
	{
		while (a[m]<x) m++;
		while (a[m-1]>=x) m--;
		return m;
	}
	
	if (a[m]>x) return cautbin2(x,st,m-1);
		else return cautbin2(x,m+1,dr);
}

int main()
{
	in>>n;
	for (i=1;i<=n;i++)
		in>>a[i];
	
	in>>t;
	for (i=1;i<=t;i++)
	{
		in>>tip>>x;
		if (tip==0) out<<cautbin0(x,1,n)<<'\n';
		if (tip==1) out<<cautbin1(x,1,n)<<'\n';
		if (tip==2) out<<cautbin2(x,1,n)<<'\n';
	}
}