#include <iostream>
#include <fstream>

#define NMAX 100001

using namespace std;
int n, m, vector[NMAX];
int mode, value;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int cautbin0(int leftt, int rightt){
	int middle = leftt + (rightt - leftt) / 2;

	if(leftt > rightt)
		return -1;

	if(vector[middle] == value && vector[middle + 1] != value){
		return middle;
	}
	
	if(vector[middle] <= value){
		return cautbin0(middle + 1, rightt);
	}

	else{
		return cautbin0(leftt, middle - 1);
	}
	
}

int cautbin1(int leftt, int rightt){
	int middle = leftt + (rightt - leftt) / 2;

	if(leftt > rightt)
		return n;

	if(vector[middle] <= value && vector[middle + 1] > value){
		return middle;
	}
	if(vector[middle] <= value){
		return cautbin1(middle + 1, rightt);
	}

	else{
		return cautbin1(leftt, middle - 1);
	}
	
}

int cautbin2(int leftt, int rightt){
	int middle = leftt + (rightt - leftt) / 2;
	
	if(vector[middle] >= value && vector[middle - 1] < value){
		return middle;
	}
	if(vector[middle] < value){
		return cautbin2(middle + 1, rightt);
	}

	else{
		return cautbin2(leftt, middle - 1);
	}
	
}

void solve(){
	
	f >> m;
	for(int i = 0; i < m; i++){
		f >> mode >> value;

		if(mode == 0){
			g << cautbin0(0, n - 1) + 1 << "\n";
		}
		
		if(mode == 1){
			g << cautbin1(0, n - 1) + 1 << "\n";
		}
		if(mode == 2){
			g << cautbin2(0, n - 1) + 1 << "\n";
		}
	}
}

int main(){
	
	f >> n;
	for(int i = 0; i < n; i++)
		f >> vector[i];
	solve();

	f.close();
	g.close();
	return 0;	
}