#include<iostream>
#include<fstream>
using namespace std;


int a[100000],n,m;

int cautbin_2(int key)
{
	int st = 1,dr = n;
	
	while(st < dr)
	{
		mij = (st+dr)/2;
	
	if(a[mij] < key)
		st = mij+1;
	else
		dr = mij;
	}
	
	mij = (st + dr)/2;
	if(a[mij] < key)
		mij++;
	
	return mij;
}

int cautbin_0(int key)
{
	int st = 1,dr = n;
	
	while(st < dr)
	{
		mij = (st+dr)/2;
		
		if(a[mij] > key)
			dr = mij;
		else
			st = mij+1;
	}
	mij = (st+dr)/2;
	
	if(a[mij] > key)
		mij--;
	if(a[mij]!=key)
		return -1;
	else
		return mij;
}


int cautbin_1(int key)
{
	int st=1,dr = n;
	
	while(st < dr)
	{
		mij = (st+dr)/2;
		
	if(a[mij] > key)
		dr = mij;
	else 
		st = mij+1;
	}
	mij = (st+dr)/2;
	
	if(a[mij] > key)
		mij--;
	return mij;
}
	
	
int main()
{
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	
	int i,x,y;
	
	fin>>n;
	
	for(i=1;i<=n;i++)
		fin>>a[i];
	
	fin>>m;
	
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
	switch(x)
	{
	case 0:
			fout<<cautbin_0(y)<<"\n";
			break;
	case 1:
			fout<<cautbin_1(y)<<"\n";
			break;
	case 2:
			fout<<cautbin_2(y)<<"\n";
	}

	}

return 0;
}