#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 100005
using namespace std;

int n, v[nmax];

int cautbin(int tip, int val) {
	int lo = 0, hi = n+1, mid;

	if(tip < 2) {
		while(hi - lo > 1) {
			mid = lo + (hi - lo) / 2;
			if(val >= v[mid]) lo = mid;
			else hi = mid;
		}
		if(tip == 0) {
			if(v[lo]==val) return lo;
			return -1;
		}
		if(tip == 1) return lo;
	}

	if(tip == 2) {
		while(hi - lo > 1) {
			mid = lo + (hi - lo) / 2;
			if(val <= v[mid]) hi = mid;
			else lo = mid;
		}
		return hi;
	}

}


int main() {
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	
	f>>n;
	for(int i=1; i<=n; i++) f>>v[i];

	int t, tip, val;
	f>>t;
	while(t--) {
		f>>tip>>val;
		g<<cautbin(tip, val)<<"\n";
	}

	return 0;
}