#include <iostream>
#include <fstream>
#define NMAX 100000

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, q, v[NMAX+10];

int binSearch1(int val)
{	int st = 1, dr = n, ans = 0;
	while(st <= dr)
		{	int mij = (st + dr) / 2;
			if(val >= v[mij]) ans = mij, st = mij + 1;
			else dr = mij - 1;
		}
	return ans;
}

int binSearch2(int val)
{	int st = 1, dr = n, ans = 0;
	while(st <= dr)
		{	int mij = (st + dr) / 2;
			if(val <= v[mij]) ans = mij, dr = mij - 1;
			else st = mij + 1;
		}
	return ans;
}

int main()
{
	fin >> n;
	for(int i=1; i<=n; i++)
		fin >> v[i];
	fin >> q;
	while(q--)
		{	int type, x;
			fin >> type >> x;
			if(type < 2)
				{	int poz = binSearch1(x);
					if(!type)
						{	if(v[poz] == x)
								fout << poz << '\n';
							else
								fout << -1 << '\n';
						}
					else
						fout << poz << '\n';
				}
			else
				{	int poz = binSearch2(x);
					fout << poz << '\n';
				}
		}
	return 0;
}