#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++){
		int s=1, d=n, sol=-1, mij;
		fin >> o >> x;
		if(o == 0){
			while(s <= d){
					mij = s + (d - s)/2;
						if(v[mij] <= x){
								s = mij + 1;
										if(v[mij]==x)
											sol = mij;
					  }else if(v[mij] > x)
								d = mij - 1;
			}
			fout << sol << '\n';
		}

		if(o == 1){
			while(s <= d){
					mij = s + (d - s)/2;
						if(v[mij] <= x){
								s = mij + 1;
								sol = mij;
						}else if(v[mij] > x)
								d = mij - 1;
			}
			fout << sol << '\n';
		}
		else if(o == 2){
			while(s <= d){
					mij = s + (d - s) / 2;
						if(v[mij] >= x){
								d = mij - 1;
								sol = mij;
						}else if(v[mij] < x)
								s = mij + 1;
			}
			fout << sol << '\n';
		}
	}	
}