#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);
	scanf("%d", &N);
	for(int i=1;i<=N;++i) {
		scanf("%d", &v[i]);
	}
	v[N+1]=INF;
	int M;
	scanf("%d", &M);
	for(int i=1;i<=M;++i) {
		int p, x;
		scanf("%d %d", &p, &x);
		if(p==0)
			printf("%d\n", bsearch0(x));
		if(p==1)
			printf("%d\n", bsearch1(x));
		if(p==2)
			printf("%d\n", bsearch2(x));
	}
	return 0;
}