#include<fstream> 
#define N 100010

using namespace std; 

long int x,y,n,m,v[N]; 

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

void citire () 
{ 
	in>>n; 
	for(int i=1;i<=n;i++) 
		in>>v[i]; 
	in>>m; 
}

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

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

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

void calcul () 
{ 
	for(int i=1;i<=m;i++) 
	{ 
		in>>x>>y; 
		if(x==0) 
			out<<cautbin0 (y); 
		if(x==1) 
			out<<cautbin1 (y); 
		if(x==2) 
			out<<cautbin2 (y); 
		out<<"\n";
	}
}

int main () 
{ 
	citire (); 
	calcul ();
	in.close (); 
	out.close (); 
	return 0; 
}