#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>

using namespace std;

#define e '\n'
#define INF 1023456789
#define ll long long

#define FILE "cautbin"

#ifdef FILE
ifstream f(string (string(FILE) + ".in").c_str());
ofstream g(string (string(FILE) + ".out").c_str());
#endif
#ifndef FILE
#define f cin
#define g cout
#endif

int i, j, n, m, k;
int v[111111];
int a, b, c;

int func1(int* sach, int needle, int left, int right) {
	if (left >= right) {
		if (sach[left] == needle) {
			return left;
		} else {
			return -1;
		}
	}

	int mid = (left+right) / 2;

	if (needle < sach[mid]) {
		return func1(sach, needle, right, mid-1);
	} else if (needle > sach[mid]) {
		return func1(sach, needle, mid+1, right);
	} else {
		return max (mid, func1(sach, needle, mid+1, right));
	}

}

int func2(int* sach, int needle, int left, int right) {
	if (left >= right) {
		if (sach[left] <= needle) {
			return left;
		} else {
			return -1;
		}
	}

	int mid = (left+right) / 2;

	if (needle < sach[mid]) {
		return func2(sach, needle, right, mid-1);
	} else if (needle > sach[mid]) {
		return max(mid, func2(sach, needle, mid+1, right));
	} else {
		return max(mid, func2(sach, needle, mid+1, right));
	}
}

int func3(int* sach, int needle, int left, int right) {
	if (left >= right) {
		if (sach[left] >= needle) {
			return left;
		} else {
			return INF;
		}
	}

	int mid = (left+right) / 2;

	if (needle < sach[mid]) {
		return min(mid, func3(sach, needle, right, mid-1));
	} else if (needle > sach[mid]) {
		return func3(sach, needle, mid+1, right);
	} else {
		return min(mid, func3(sach, needle, left, mid-1));
	}
}

int main() {

	f >> n;

	for (i=1; i<=n; i++) {
		f >> v[i];
	}

	f >> m;

	while (m--) {
		f >> a >> b;

		if (a == 0) {
			int result = func1(v, b, 1, n);
			g << result << e;
		} else if (a == 1) {
			int result = func2(v, b, 1, n);
			g << result << e;
		} else if (a == 2) {
			int result = func3(v, b, 1, n);
			g << result << e;
		}
	}

	return 0;

}