#include <fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,v[100005],mij,max,k;



/*0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta 
valoare nu se gaseste in sir*/

/*1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x 
in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x*/

/*2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu 
x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x*/

int cautadoi(int y,int st,int dr)
{
	if(st>dr)
		return -1;
	else
	{
		mij=(st+dr)/2;
		if(v[mij]==y)
		{
			k=mij;
			while(k!=1)
				if(v[k-1]==y)
					k--;
				else
					return k;
		}
		else
			if(v[mij]>y)			
				cautadoi(y,1,mij);
			else
				cautadoi(y,mij,dr);				
	}
	if(v[mij]>y)
		return v[mij];
		else
		{
			k=mij;
			while(k!=n)
				if(v[k+1]<y)
					k++;
				else
					return k;
		}
}


int cautaunu(int y,int st,int dr)
{
	if(st>dr)
		return -1;
	else
	{
		mij=(st+dr)/2;
		if(v[mij]==y)
		{
			k=mij;
			while(k!=n)
				if(v[k+1]==y)
					k++;
				else
					return k;
		}
		else
			if(v[mij]>y)			
				cautaunu(y,1,mij);
			else
				cautaunu(y,mij,dr);				
	}
	if(v[mij]<y)
		return v[mij];
		else
		{
			k=mij;
			while(k!=0)
				if(v[k-1]>y)
					k--;
				else
					return k;
		}
}

int cautazero(int y,int st,int dr)
{
	//Returneaza pozitia cea mai mare
	if(st>dr)
		return -1;
	else
	{
		mij=(st+dr)/2;
		if(v[mij]==y)
		{ 
			k=mij; 
			while(k!=n)
				if(v[k+1]==y) k++;
				else
					return k;
		}
		else
			if(v[mij]>y)
				cautazero(y,st,mij);
			else
				if(v[mij]<y)
					cautazero(y,mij,dr);
	}		
	return -1;
}

int main()
{
	int i,x,y;
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		if(x==0)
			g<<cautazero(y,1,n)<<'\n';
		else
			if(x==1)
				g<<cautaunu(y,1,n)<<'\n';
			else
				g<<cautadoi(y,1,n)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}