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

int n, v[nmax];

int cautbin(int tip, int val) {
	//cea mai mare pozitie pe care se afla x

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

	if(tip == 0) {
		if(v[lo]==val) return lo;
		return -1;
	}
	if(tip == 1) return lo;
}


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;
}