#include <iostream>
#include <fstream>
using namespace std;
#define N 100010
int v[N];
int bsearch0(int left, int right, int key){
	int m;
	while(left <= right){
		 m = (left + right)/2;
		if(v[m] <= key){
			left = m + 1;
		}else{
			right = m - 1;
		}
	}
	m = (left + right)/2;
	if(v[m] > key){
		m--;
	} 
	if(v[m] == key){
		return m;
	} 
   return -1;
}

int bsearch1(int left, int right, int key){
    int m;
    while(left < right){
    	m = (left + right)/2;
    	if(v[m] <= key){
            left = m + 1;
    	}else{
    		right =  m;
    	}
    }
    m = (left + right)/2;
    if(v[m] > key){
    	m--;
    }
    return m;
}

int bsearch2(int left, int right, int key){
	int m;
	while(left < right){
		m = (left + right)/2;
		if(v[m] < key){
			left = m + 1;
		}else{
			right = m;
		}
	}
	m = (left + right)/2;
	if(v[m] < key){
		m++;
	}
	return m;

}

int main(){
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	int n;
	fin >> n;
	for(int i = 1; i <= n; i++){
		fin >> v[i];
	}
	int num;
	fin >> num;
	int tip, val;
	while(num--){
		fin >> tip >> val;
		if(tip == 0){
			fout << bsearch0(1, n, val) << '\n';
		}
		if(tip == 1){
			fout << bsearch1(1, n, val) << '\n';
		}
		if(tip == 2){
			fout << bsearch2(1, n, val) << '\n';
		}

	}
	return 0;

}