#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, v[100005], m, o, x;

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

	fin >> m;
	for(int i = 1; i <= m; i++){
		fin >> o >> x;
		int st = 1;
		int dr = n;
		if(o == 0){
			int maxp = -1;
			while(st <= dr){
				int mij = st + (dr - st) / 2;
				if(v[mij] <= x){
					st = mij + 1;
					if(v[mij]==x && mij>maxp)
						maxp=mij;
				}else if(v[mij] > x)
					dr = mij - 1;
			}
			fout << maxp << '\n';
		}
		if(o == 1){
			int maxp = -1;

			while(st <= dr){
				int mij = st + (dr - st) / 2;
				if(v[mij] <= x){
					st = mij + 1;
					if(x >= v[mij] && mij > maxp)
							maxp=mij;
				}else if(v[mij] > x)
					dr = mij - 1;
			}
			fout << maxp << '\n';
		}
		else if(o == 2){
			int maxp = n+1;
			while(st <= dr){
				int mij = st + (dr - st) / 2;
				if(v[mij] >= x){
					dr = mij - 1;
					if(x <= v[mij] && mij < maxp)
							maxp = mij;
				}else if(v[mij] < x)
					st = mij + 1;
			}
			fout << maxp;
		}
	}	
}