#include<stdlib.h>
#include<fstream>
#include<iostream>


using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int cautare0(int *v,int n,int x)
{
	int a=1,b=n,mij=(a+b)/2;
	while(a<=b)
	{
		if(v[mij]<=x)
			a=mij+1;
		else
			b=mij-1;
		mij=(a+b)/2;
	}
	if(v[mij]>x)
		mij--;
	if(v[mij-1]==x)
		return mij;
	else
		return -1;
}
int cautare1(int *v,int n,int x)
{
	int a=1,b=n,mij=(a+b)/2;
	while(a<b)
	{
		if(v[mij]<=x)
			a=mij+1;
		else
			b=mij;
		mij=(a+b)/2;
	}
	if(v[mij]>x)
		mij--;
	return mij;
}
int cautare2(int *v,int n,int x)
{
	int a=1,b=n,mij=(a+b)/2;
	while(a<b)
	{
		if(v[mij]<x)
			a=mij+1;
		else
			b=mij;
		mij=(a+b)/2;
	}
	if(v[mij]>x)
		mij+1;
	return mij;
}
int main()
{
	int *v,n,i,m,opt,x;
	in>>n;
	//alocarea vectorului de n elemente
	v=( int *)malloc((n+1)*sizeof( int ));
	for(i=1;i<=n;i++)
		in>>v[i];
	in>>m;
	for(i=1;i<=m;i++)
	{
		in>>opt;
		in>>x;
		if(opt==0)
			out<<cautare0(v,n,x)<<"\n";
		else
			if(opt==1)
				out<<cautare1(v,n,x)<<"\n";

			else
				out<<cautare2(v,n,x)<<"\n";
	}
	//eliberare memorie
	free(v);
	in.close();
	out.close();
	return 0;
}