#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <math.h>
#include <fstream>
using namespace std;

vector <string> splitting_string(std::istringstream line, char delimiter){
	std::vector<std::string> splits;
	std::string string;
	while( std::getline( line , string , delimiter ) )
	{
		std::cout<<  string  <<endl;
		//push split strings into vector.
	    splits.push_back( string );
	}
	return splits;
}

int BS(vector <int> array, int n, int command, int value)
{
	int position;
	if( command <= 1) position = -1;
	else position = n-1;
	int i = 0;
	int j = array.size() - 1;
	int mid;
	while ( i <= j )
	{

			mid = i + (j - i)/2;
			if ( array[mid] < value)
			{
				i = mid + 1;
				if (command == 1) position = mid;
			}
			else if ( array[mid] > value )
			{
				j = mid - 1;
				if (command == 2) position = mid;
			}
			else
			{
				position = mid;
				if (command <= 1)	i = mid + 1;
				else if (command == 2) j = mid - 1;
			}

	}

	return position;

}

int main() {
	fstream myfile("cautbin.in",  std::ios_base::in);
	fstream myfile1("cautbin.out", std::ios_base::out);
	int n;
	int command;
	int value, value1;
	myfile >> n;
	vector <int> array(n);
	for ( int i = 0; i < n; i++ )
	{
		myfile >> array[i];
	}
	myfile >> value1;
	int position;
	int i, j = 0;
	while (value1 != 0)
	{
		myfile >> command;
		myfile >> value;
		position = BS(array, n, command, value);
		if (position == -1)
			myfile1<< position<<endl;
		else
			myfile1<< position+1 <<endl;
		value1--;
	}
    return 0;
}