#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=0,b=n-1, mij=(a+b)/2,ok=0,i;
	while(a<b && ok==0)
	{
		//in cazul in care este egal si cel de dupa nu este sau este ultimul element retinem
		if((v[mij]==x&&mij==n)||(v[mij]==x&&v[mij+1]!=x))
		{
			ok=1;
			i=mij;
		}
		//alegem jumatatea buna
		else
			if(v[mij]<=x)
				a=mij;
			else
				if(v[mij]>=x)
					b=mij;
		mij=(a+b)/2;
	}
	if(ok==1)
		return i+1;
	else
		return -1;
}
int cautare1( int *v,int n,int x)
{
	int a=0,b=n-1, mij=(a+b)/2,ok=0,i;
	while(a<b && ok==0)
	{	
		//in cazul in care este egal si cel de dupa nu este sau este ultimul element retinem
		if((v[mij]<x&&mij==n)||(v[mij]<x&&v[mij+1]>x))
		{
			ok=1;
			i=mij;
		}
		//alegem jumatatea buna
		else
			if(v[mij]<=x)
				a=mij;
			else
				if(v[mij]>=x)
					b=mij;
		mij=(a+b)/2;
	}
	return i+1;
}
int cautare2( int *v,int n,int x)
{
	int a=0,b=n-1, mij=(a+b)/2,ok=0,i;
	while(a<b && ok==0)
	{
		cout<<mij;
		//in cazul in care este egal si cel de dupa nu este sau este ultimul element retinem
		if((mij>0&&(v[mij]==x&&v[mij-1]!=x))||(v[mij]<x&&v[mij+1]>x))
		{
			ok=1;
			i=mij+1;
		}
		//alegem jumatatea buna
		else
			if(v[mij]<=x)
				a=mij;
			else
				if(v[mij]>=x)
					b=mij;
		mij=(a+b)/2;
	}
	return i;
}

int main()
{
	int *v,n,i,m,opt,x;
	in>>n;
	//alocarea vectorului de n elemente
	v=( int *)malloc(n*sizeof( int ));
	for(i=0;i<n;i++)
		in>>v[i];
	in>>m;
	for(i=0;i<m;i++)
	{
		in>>opt;
		in>>x;
		if(opt==0)
		out<<cautare0(v,n,x)<<"\t";
		else
			if(opt==1)
				out<<cautare1(v,n,x)<<"\t";

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