//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

//#include <iostream>
#include <fstream>
ifstream cin("cautbin.in"); ofstream cout("cautbin.out");

//VARIABLES

int n, m, c, nr;
long long v[100005];


//FUNCTIONS

int caut_bin0(int nr) {
	int st = 1, dr = n;
	int ans = -1;
	while (st <= dr) {
		int mid = st + dr;
		mid /= 2;

		if (v[mid] == nr) {
			ans = mid;
		}

		if (v[mid] <= nr) {
			st = mid + 1;
		}

		else dr = mid - 1;
	}
	return ans;
}

int caut_bin1(int nr) {
	int st = 1, dr = n;
	int ans = 0;
	while (st <= dr) {
		int mid = st + dr;
		mid /= 2;

		if (v[mid] <= nr) {
			ans = mid;
			st = mid + 1;

		}

		else dr = mid - 1;
	}
	return ans;
}

int caut_bin2(int nr) {
	int st = 1, dr = n;
	int ans = 0;
	while (st <= dr) {
		int mid = st + dr;
		mid /= 2;

		if (v[mid] >= nr) {
			ans = mid;
			dr = mid - 1;
		}

		else st = mid + 1;
	}
	return ans;
}


//MAIN
int main() {

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

	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> c >> nr;

		if (c == 0) cout << caut_bin0(nr) << '\n';

		else if (c == 1) cout << caut_bin1(nr) << '\n';

		else if (c == 2) cout << caut_bin2(nr) << '\n';
	}

	return 0;
}