#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
ifstream ff("cautbin.in");
ofstream gg("cautbin.out");

#define max 100001
int n, m, aa[max];

int cb0(int v){
	int l = 1, r = n, m;
	while(r-l>1){
		m=(l+r)/2;
		if(aa[m]<=v)l=m; else r=m-1;
	}
	return aa[r]==v?r:aa[l]==v?l:-1;
}

int cb1(int v){
	int l = 1, r = n, m;
	while(r-l>1){
		m=(l+r)/2;
		if(aa[m]<=v)l=m; else r=m-1;
	}
	return aa[r]<=v?r:l;
}

int cb2(int v){
	int l = 1, r = n, m;
	while(r-l>1){
		m=(l+r)/2;
		if(aa[m]>=v)r=m; else l=m+1;
	}
	return aa[l]>=v?l:r;
}

int main(){
	int op, x;
	ff >> n;
	for(int i=1;i<=n;i++) ff >> aa[i];
	ff >> m;
	for(int i=1;i<=m;i++){
		ff >> op >> x;
		if(op==0){ gg << cb0(x) << "\n"; } else
		if(op==1){ gg << cb1(x) << "\n"; } else
		if(op==2){ gg << cb2(x) << "\n"; }
	}
	return 0;
}