#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<vector>
#include<math.h>
#include<fstream>
#include<string>
#include<limits.h>
#include<climits>
#include<algorithm>
#include<unordered_set>



using namespace std;
vector<int>nums;
 int cautbin0( int x)
{
	 int lo = 0;
	 int hi = nums.size() - 1;
	 int ok = 0;
	 int res = -1;
	 while (lo <= hi)
	 {
		 int mid = (int)(lo + ((double)hi - lo) / 2);
		 if (nums[mid]>x)
		 {
			 hi = mid - 1;
		 }
		 else {
			 if (nums[mid] == x) {
				 ok = 1;
				 res = mid;
			 }
			 lo = mid + 1;
		 }
	 }
	 if (ok == 0)
		 return -1;
	 return res;
}
 int cautbin1( int x)
{
	 int lo = 0;
	 int hi = nums.size() - 1;
	 int res = -1;
	 while (lo <= hi)
	 {
		 int mid = (int)(lo + ((double)hi - lo) / 2);
		 if (nums[mid]>x)
		 {
			 hi = mid - 1;
		 }
		 else {
			 if (nums[mid] <= x) {
				 res = mid;
			 }
			 lo = mid + 1;
		 }
	 }
	 return res;
}
 int cautbin2(int x)
{
	 int lo = 0;
	 int hi = nums.size() - 1;
	 int res = -1;

	 while (lo <= hi)
	 {
		 int mid = (int)(lo + ((double)hi - lo) / 2);
		 if (nums[mid]<x)
			 lo = mid + 1;
		 else {
			 if (nums[mid] >= x)
			 {
				 res = mid;
			 }
			 hi = hi - 1;
		 }
	 }
	 return res;
}
int main()
{
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int inter;
		scanf("%d", &inter);
		nums.push_back(inter);
	}
	int querries;
	scanf("%d", &querries);
	for (int i = 0; i < querries; i++)
	{
		int command;
		scanf("%d", &command);
		int x;
		scanf("%d", &x);
		int res=0;
		switch (command) {
		case 0:
			res = cautbin0(x);
			if (res != -1)
			{
				res += 1;
			}
			printf("%d\n", res);
			break;
		case 1:
			printf("%d\n",cautbin1(x) + 1);
			break;
		case 2:
			printf("%d\n", cautbin2(x) + 1);
		}
	}
	return 0;

	/*ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	int n;
	in >> n;
	for (int i = 0; i < n; i++)
	{
		int inter;
		in >> inter;
		nums.push_back(inter);
	}
	int querries;
	in >> querries;
	for (int i = 0; i < querries; i++)
	{
		int command;
		in >> command;
		int x;
		in >> x;
		int res = 0;
		switch (command) {
		case 0:
			res = cautbin0(x);
			if (res != -1)
			{
				res += 1;
			}
			out << res << endl;
			break;
		case 1:
			out << cautbin1(x) + 1 << endl;
			break;
		case 2:
			out << cautbin2(x) + 1 << endl;
		}
	}
	in.close();
	out.close();
	return 0;*/
}