#include <iostream>
#include <fstream>

using namespace std;

int cautare_bin0(int st, int dr, int *v, int y)
{
	if(st>dr)
		return -1;
	if(y==v[st+(dr-st)/2])
	{
		int poz=st+(dr-st)/2;
		while(v[poz]==y)
			poz++;
		return poz;
	}
	else
		if(y<v[st+(dr-st)/2])
			cautare_bin0(st,st+((dr-st)/2)-1,v,y);
		else if(y>v[st+(dr-st)/2])
			cautare_bin0((st+(dr-st)/2)+1,dr,v,y);
}

int cautare_bin1(int st, int dr, int *v, int y)
{
	if(st>dr)
		return -1;
	if(y>=v[st+(dr-st)/2])
	{
		int poz=st+(dr-st)/2;
		while(v[poz]<=y)
			poz++;
		return poz;
	}
	else
		if(y<v[st+(dr-st)/2])
			cautare_bin0(st,st+((dr-st)/2)-1,v,y);
		else if(y>v[st+(dr-st)/2])
			cautare_bin0((st+(dr-st)/2)+1,dr,v,y);
}

int cautare_bin2(int st, int dr, int *v, int y)
{
	if(st>dr)
		return -1;
	if(y<=v[st+(dr-st)/2])
	{
		int poz=st+(dr-st)/2;
		while(v[poz]>=y)
			poz--;
		return poz+2;
	}
	else
		if(y<v[st+(dr-st)/2])
			cautare_bin0(st,st+((dr-st)/2)-1,v,y);
		else if(y>v[st+(dr-st)/2])
			cautare_bin0((st+(dr-st)/2)+1,dr,v,y);
}

int main()
{
	ifstream input("cautbin.in");
	if(input)
	{
		ofstream output("cautbin.out");
		int N;
		input>>N;
		int *v;
		v=new int[N];
		for(int i=0;i<N;i++)
			input>>v[i];
		int M,x,y;
		input>>M;
		for(int i=0;i<M;i++)
		{
			input>>x>>y;
			if(x==0)
				output<<cautare_bin0(0,N-1,v,y)<<"\n";
			else if(x==1)
				output<<cautare_bin1(0,N-1,v,y)<<"\n";
			else if(x==2)
				output<<cautare_bin2(0,N-1,v,y)<<"\n";
		}
	}
	return 0;
}