#include <bits/stdc++.h>
using namespace std;

const int NMAX=1e5+1, INF=1e9;
int N, v[NMAX+2];

int bsearch0(int x) {
	int poz=N+1, st=1, dr=N, mj;
	while(st<=dr) {
		mj=(st+dr)/2;
		if(v[mj]>x) {
			poz=mj;
			dr=mj-1;
		}
		else
			st=mj+1;
	}
	--poz;
	if(v[poz]==x)
		return poz;
	return -1;
}

int bsearch1(int x) {
	int st=1, dr=N, mj, poz=N+1;
	while(st<=dr) {
		mj=(st+dr)/2;
		if(v[mj]>x) {
			poz=mj;
			dr=mj-1;
		}
		else
			st=mj+1;
	}
	--poz;
	return poz;
}

int bsearch2(int x) {
	int st=1, dr=N, mj, poz=0;
	while(st<=dr) {
		mj=(st+dr)/2;
		if(v[mj]<x) {
			poz=mj;
			st=mj+1;
		}
		else
			dr=mj-1;
	}
	++poz;
	return poz;
}

int main() {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	cin>>N;
	for(int i=1;i<=N;++i) {
		cin>>v[i];
	}
	v[N+1]=INF;
	int M;
	cin>>M;
	for(int i=1;i<=M;++i) {
		int p, x;
		cin>>p>>x;
		if(p==0)
			cout<<bsearch0(x)<<'\n';
		if(p==1)
			cout<<bsearch1(x)<<'\n';
		if(p==2)
			cout<<bsearch2(x)<<'\n';
	}
	return 0;
}