#include <iostream>
#include <stdio.h>
#include <fstream>

using namespace std;

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

const int NMAX = 100001;

int arr[NMAX];
int n;

int caut_bin(int code, int x){

	int lo = 0, hi = n-1, mid;

	if( code == 0){

		while(lo < hi){
			mid = lo + (hi-lo)/2;
			if(arr[mid] <= x)
				lo = mid+1;
			else
				hi = mid-1;
		}
		if(arr[lo] != x)
			lo --;
		if(arr[lo] != x)
			return -1;
		else
			return lo+1;
	}
	else if( code == 1){
	
		while(lo < hi){
			mid = lo + (hi-lo)/2;
			if(arr[mid] <= x)
				lo = mid+1;
			else
				hi = mid-1;
		}
		if(arr[lo] > x)
			lo--;
		return lo+1;
	}
	else{
		
		while(lo < hi){
			mid = lo + (hi-lo)/2;
			if(arr[mid] < x)
				lo = mid+1;
			else 
				hi = mid;
		}
		return lo+1;
	
	}
}



int main(){

	fin >> n;
	for(int i=0; i<n; ++i)
		fin >> arr[i];
	int t, code, nr;
	fin >> t;
	for(int i=0; i<t; ++i){
		fin >> code >> nr;
		fout << caut_bin(code, nr) << "\n";
	}
	return 0;
}