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

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

#define dmax 100001

int v[dmax], n;

int cb0(int x){
	int st=0, dr=n+1, m, r=-1;
	while (dr-st>1){
		m=(st+dr)/2;
		if (v[m]==x){
			r=max(r, m);
			st=m;
		}
		else if (v[m]<x)
			st=m;
		else
			dr=m;
	}
	return r;
}

int cb1(int x){
	int st=0, dr=n+1, m, r=-1;
	while (dr-st>1){
		m=(st+dr)/2;
		if (v[m]<=x){
			r=max(r, m);
			st=m;
		}
		else
			dr=m;
	}
	return r;
}

int cb2(int x){
	int st=0, dr=n+1, m, r=1e8;
	while (dr-st>1){
		m=(st+dr)/2;
		if (v[m]>=x){
			r=min(r, m);
			dr=m;
		}
		else
			st=m;
	}
	return r;
}

int main()
{
	int i, m, op, val;
	fin>>n;
	for (i=1;i<=n;i++)
		fin>>v[i];
		
	fin>>m;
	
	for (i=1;i<=m;i++){
		fin>>op>>val;
		if (op==0)
			fout<<cb0(val);
		else if (op==1)
			fout<<cb1(val);
		else
			fout<<cb2(val);
		fout<<'\n';
	}
	fin.close();
	fout.close();
	return 0;
}