//cautare binara 9.01.2012
#include<iostream>
#include<fstream>
using namespace std;
const int nmax=100001;
int n,v[nmax],m;

int cautbin0 (int x) //poz cea mai mare pe care se afla x
{
	int st=1,dr=n,mij;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (v[mij]==x) //daca exista mai multi x in vector
		{			
			if (mij+1<=n) //daca indicele nu depaseste vectorul
				if (v[mij+1]!=x) return mij; 
				else ;
			else return mij;
		}
		if (v[mij]<=x) st=mij+1;
		else dr=mij-1;
	}
	return -1;
}
int cautbin1 (int x) //cea mai mare pozitie a unui el din vector <= x
{
	int st=1,dr=n,mij;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (st==n) return n; 
		if (v[mij]==x) 
		{			
			if (mij+1<=n) //daca indicele nu depaseste vectorul
				if (v[mij+1]!=x) return mij; 
				else ;
			else return mij;
		}
		if (v[mij]<x && v[mij+1]>x) return mij; //daca se afla intre v[mij] si v[mij+1]
		if (v[mij]<=x) st=mij+1;
		else dr=mij-1;
	}
	return -1;
}
int cautbin2 (int x) //cea mai mica poz a unui el din vector cu v[] >= x
{
	int st=1,dr=n,mij;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (dr==1) return 1;
		if (v[mij]==x) 
		{			
			if (mij-1>=1) //daca indicele nu depaseste vectorul
				if (v[mij-1]!=x) return mij; 
				else ;
			else return mij;
		}
		if (v[mij-1]<x && v[mij]>x) return mij; //daca se afla intre v[mij-1] si v[mij]
		if (v[mij]>=x) dr=mij-1;
		else st=mij+1;
	}
	return -1;
}
int main ()
{
	int tip,x;
	ifstream fin ("cautbin.in");
	ofstream fout("cautbin.out");
	
	fin>>n;
	for (int i=1;i<=n;++i)
		fin>>v[i];
	
	fin>>m;
	for (int i=1;i<=m;++i)
	{
		fin>>tip>>x;
		if (tip==0)	fout<<cautbin0(x)<<'\n';
		else if (tip==1) fout<<cautbin1(x)<<'\n';
		else if (tip==2) fout<<cautbin2(x)<<'\n';
		else cout<<"n-avem/n";
	}
	fin.close();
	fout.close();
	return 0;
}