#include <fstream.h>

int n,v[100001];

int op0(int key),op1(int key),op2(int key);


int main()
{
	int i,op;
	
	ifstream in("cautbin.in"); 
	ofstream out("cautbin.out");
	in>>n;
	for(i=1;i<=n;++i) in>>v[i];
	for(i=1;i<=n;++i)
	{
		in>>op;
		switch(op)
		{
			case 0: in>>op; out<<op0(op)<<'\n'; break;
			case 1: in>>op; out<<op1(op)<<'\n'; break;
			case 2: in>>op; out<<op2(op)<<'\n'; break;
		}
	}
	in.close(); out.close();
	
	return 0;
}

int op0(int key)
{
	int mid,left=1,right=n,result=-1;
	
	while(left<=right)
	{
		mid=left+(right-left)/2;
		if(v[mid]==key){ result=mid; left=mid+1; }
		else
			if(v[mid]<key) left=mid+1;
			else right=mid-1;
	}
	
	return result;
}

int op1(int key)
{
	int mid,left=1,right=n,result;
	
	while(left<=right)
	{
		mid=left+(right-left)/2;
		if(v[mid]<=key){ result=mid; left=mid+1; }
		else  right=mid-1;
	}
	
	return result;
}

int op2(int key)
{
	int mid,left=1,right=n,result;
	
	while(left<=right)
	{
		mid=left+(right-left)/2;
		if(v[mid]>=key){ result=mid; right=mid-1; }
		else left=mid+1;
	}
	
	return result;
}