/*Cautare binara

Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:
 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
Date de intrare

Pe prima linie a fisierului de intrare cautbin.in se afla numarul N reprezentand numarul de elemente ale sirului. Pe urmatoarea linie se gasesc N numere reprezentand elementele sirului. Linia a treia contine numarul M reprezentand numarul de intrebari. Apoi urmeaza M linii, fiecare cu unul dintre cele 3 tipuri de intrebari.
Date de iesire

In fisierul de iesire cautbin.out se vor afisa M linii reprezentand raspunsul la cele M intrebari.
Restrictii
1 < N < 100 000
1 < M < 100 000
Elementele sirului vor fi numere strict pozitive si se vor incadra pe 31 de biti
cautbin.in	                          cautbin.out
 5                                          4
 1 3 3 3 5                                  4
 3                                          2
 0 3
 1 3                                        
 2 3
*/
#include<fstream>
using namespace std;
int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	int i,n,v[100000],inc,sf,x,t,m;
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>t>>x;
		if(t!=2)
		{
			inc=1;
			sf=n;
			while(inc!=(sf-1))
			{
				if(v[(inc+sf)/2]>x)
					sf=(inc+sf)/2;
				else inc=(inc+sf)/2;
			}
			if(t==0)
			{
				if(v[inc]==x)
					g<<inc<<endl;
				if(v[sf]==x)
					g<<sf<<endl;
				if((v[inc]!=x)&&(v[sf]!=x))
					g<<-1<<endl;
			}
			if(t==1)
			{
				if(v[sf]==x)
					g<<sf<<endl;
				else 
				{
					if(v[sf]<x)
						g<<sf<<endl;
					else  g<<inc<<endl;
				}
			}		
		}
		if(t==2)
		{
			inc=1;
			sf=n;
			while(inc!=sf-1)
			{
				if(v[(inc+sf)/2]>=x)
					sf=(inc+sf)/2;
				else inc=(inc+sf)/2;
			}
			if(v[inc]==x)
				g<<inc<<endl;
			else
			{
				if(v[inc]>x)
					g<<inc<<endl;
				else g<<sf<<endl;
			}
		}
		
	}
}