/*
 * cautareBin.c
 * 
 * Copyright 2019 Horatiu Tarcea <thr@MontranHT>
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02110-1301, USA.
 * 
 * 
 */

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int main(int argc, char **argv)
{
	int n, pbn;
	fin >> n;
	int a[n+1];
	for (int i = 1; i<= n; i++)
	{
		fin >> a[i];
	}
	fin >> pbn;
	for(int i = 0; i < pbn; i++)
	{
		int pb, val;
		fin >> pb >> val;
		int st, dr, mid;
		st = 1;
		dr = n;
		int ans = -1;
		if(pb == 0) 
		{
			//problema 0
			if(a[dr] == val)
			{
				ans = dr;
				cout << "out";
			}
			else 
			{
				while(st < dr)
				{
					mid = (st + dr) / 2;
					if(a[mid] <= val)
					{
						st = mid + 1;
						if(a[mid] == val) ans = mid;
					}
					else
					{
						dr = mid;
					}
				}
			}
			fout << ans << endl;
		} 
		else if(pb == 1)
		{
			//problema 1
			if(a[dr] <= val)
			{
				ans = dr;
			}
			else
			{ 	
				while(st < dr)
				{
					mid = (st + dr) / 2;
					if(a[mid] <= val)
					{
						st = mid + 1;
						ans = mid;
					}
					else
					{
						dr = mid;
					}
				}
			}
			fout << ans << endl;
		}
		else if(pb == 2)
		{
			//problema 2
			while(st < dr)
			{
				mid = (st + dr) / 2;
				if(a[mid] < val)
				{
					st = mid + 1;
				}
				else
				{
					dr = mid;					
					ans = mid;
				}
			}
			if(a[dr] <= val) ans = dr;
			fout << ans << endl;
		}
	}
	
	return 0;
}