#include <iostream>
#include <stdio.h>

using namespace std;

int m, n, v[100005];

int bsearch0 (int x) {
	int mid, l = 0, r = n;
	
	while (l < r) {
		mid = (l + r) / 2;
		
		if (v[mid] == x) {
			break;
		} else if (x < v[mid]) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	if (v[mid] == x) {
		while (v[mid+1] == x) {
			++mid;
		}
		return mid;
	}
	
	return -1;
}

int bsearch1 (int x) {
	int i = 0;
	while (i < n && v[i] <= x) {
		i = (n + i) / 2;
	}
	
	while (v[i] > x) {
		--i;
	}
	
	return i;
}

int bsearch2 (int x) {
	int i = n - 1;
	
	while (i > 0 && v[i] >= x) {
		i /= 2;
	}
	
	while (v[i] < x) {
		++i;
	}
	
	return i;
}
	
int main (void) {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int x, c;
		cin >> c >> x;
		
		if (c == 0) {
			cout << bsearch0(x) + 1 << '\n';
		} else if (c == 1) {
			cout << bsearch1(x) + 1<< '\n';
		} else {
			cout << bsearch2(x) + 1 << '\n';
		}
	}
	
	return 0;
}