#include <iostream>
#include <fstream>
using namespace std;

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

int a[100005];

int main(){
	int n; 
	fin >> n; 
	for(int i=1; i<=n; ++i){
		fin >> a[i];
		}
	int m;
	
	fin >> m;
	
	for(int i=1; i<=m; ++i){
		int op, x, result, mid, l=1, r=n;
		fin >> op >> x;
		result=-1;
		if(op == 0){
			while(l<=r){
				mid = (l+r) / 2;
				if(a[mid]==x){
					result=mid;
					l=mid+1;
					}
				else if(a[mid]<x){
					l=mid+1;
					}
				else if(a[mid]>x){
					r=mid-1;
					}
				}
			}
		if(op == 1){
			while(l<=r){
				mid = (l+r) / 2;
				if(a[mid]<=x){
					result=mid;
					l=mid+1;
					}
				else if(a[mid]>x){
					r=mid-1;
					}
				}
			}
		if(op == 2){
			while(l<=r){
				mid = (l+r) / 2;
				if(a[mid]>=x){
					result=mid;
					r=mid-1;;
					}
				else if(a[mid]<x){
					l=mid+1;
					}
				}
			}
		fout << result << '\n';
	}
	
	 return 0;
	
	}