#include <fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long long 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*/



void cauta(int x,int y,int st,int dr)
{
	
	
		{mij = st + (dr-st)/2;
		if(v[mij]==y)
		{ 
			 k=mij;
			while(k!=n)
				if(v[k+1]==y) k++;
				
					g<< k<<'\n';
		}
		else
			if(v[mij]>y)
				cauta(x,y,st,mij-1);
			else
				if(v[mij]<y)
					cauta(x,y,mij+1,dr);
	
	if(x==0&&v[mij]!=y)		
	g<< -1<<'\n';
	else if(x==1)
	{k=mij;
		while(v[k]<y)k++;
	
		while(v[k]>=y)if(v[k+1]>=y)k++;
		g<<v[k]<<'\n';
	}
	else {k=mij;
		while(v[k]>y)k--;
	
		while(v[k]<=y)if(v[k+1]<=y)k++;
		g<<v[k]<<'\n';
	}

		}
}

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;
		
			cauta(x,y,1,n);
	}
	f.close();
	g.close();
	return 0;
}