#include<iostream>
#include<fstream>

using namespace std;

int n,v[100005];

int bin0(int val)
{
	int step,i,temp;
	for(step=1; step<n; step<<=1) ;
	for(i=0; step; step>>=1)
	{
		temp=i+step;
		if(temp<n && v[temp]<=val)
			i+=step;
	}
	if(v[i]==val) return 1+i;
	else return -1;
}

int bin1(int val)
{
	int step,i,temp;
	for(step=1; step<n; step<<=1) ;
	for(i=0; step; step>>=1)
	{
		temp=i+step;
		if(temp<n && v[temp]<=val)
			i+=step;
	}
	return 1+i;
}

int bin2(int val)
{
	int step,i,temp;
	if(v[0]>=val) return 0;
	for(step=1; step<n; step<<=1) ;
	for(i=n; step; step>>=1)
	{
		temp=i-step;
		if(temp>0) if(temp<n && v[temp]>=val)
			i-=step;
	}
	return 1+i;
}


int main()
{
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
		
	fin>>n;
	for(int i=0;i<n;++i)
		fin>>v[i];
	
	int m,a,t;
	fin>>m;
	for( ; m; --m)
	{
		fin>>t>>a;
		if(t==0) fout<<bin0(a)<<endl;
		else if(t==1) fout<<bin1(a)<<endl;
		else if(t==2) fout<<bin2(a)<<endl;
	}
	
	return 0;
}