//ALEX ENACHE

#include <vector>
#include <algorithm>

#include <math.h>
#include <iomanip>
#include <bitset>

#include <queue>
#include <deque>
#include <stack>

#include <map>
#include <unordered_map>
#include <set>
#include <unordered_map>

#include <random>
#include <time.h>
#include <assert.h>

using namespace std;

//-----------------------------------------------------------------

#include <iostream> 
#pragma warning(disable:4996)

int n;
int v[100100];

int caut_bin(int val) {
	int pos = 0;
	for (int bit = 17; bit >= 0; bit--) {
		int next_pos = pos + (1 << bit);
		if (next_pos <= n && v[next_pos] <= val) {
			pos = next_pos;
		}
	}
	return pos;
}

int caut_bin_bigger(int val) {
	int pos = n;
	for (int bit = 17; bit >= 0; bit--) {
		int next_pos = pos - (1 << bit);
		if (next_pos >= 1 && v[next_pos] >= val) {
			pos = next_pos;
		}
	}
	return pos;
}


int main() {

	freopen("cautbin.in", "r", stdin); freopen("cautbin.in", "w", stdout);

	cin >> n;

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

	int t;
	cin >> t;

	while (t--) {
		int tip , val;
		cin >> tip>>val;
		if (tip == 0) {
			int ans = caut_bin(val);
			if (v[ans] != val) {
				ans = -1;
			}
			cout << ans << '\n';
		}
		if (tip == 1) {
			cout << caut_bin(val) << '\n';
		}
		if (tip == 2) {
			cout << caut_bin_bigger(val) << '\n';
		}

	}

	return 0;
}