#include <cstdio>
using namespace std;

const int nMax = 100001;

int v[nMax], n;

inline int bin_search0(int x) // cea mai mare pozitie pe care apare x
{
	int st=1, dr=n, mij;
	while (st<=dr) {
		mij=(st+dr)>>1;
		v[mij]<=x ? st=mij+1 : dr=mij-1;
	}
	mij=(st+dr)>>1;
	if (v[mij]>x) --mij;
	return (v[mij]==x ? mij : -1);
}

inline int bin_search1(int x) // cea mai mare pozitie pe care apare un element <= x
{
	int st=1, dr=n, mij;
	while (st<dr) {
		mij=(st+dr)>>1;
		v[mij]<=x ? st=mij+1 : dr=mij;
	}
	mij=(st+dr)>>1;
	if (v[mij]>x) --mij;
	return mij;
}

inline int bin_search2(int x) // cea mai mica pozitie pe care apare un element >= x
{
	int st=1, dr=n, mij;
	while (st<dr) {
		mij=(st+dr)>>1;
		v[mij]<x ? st=mij+1 : dr=mij;
	}
	mij=(st+dr)>>1;
	if (v[mij]<x) ++mij;
	return mij;
}

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]);
	
	int m, tip, val;
	scanf("%d",&m); ++m;
	while (--m) {
		scanf("%d%d",&tip,&val);
		if (tip==0)
			printf("%d\n",bin_search0(val));
		else if (tip==1)
			printf("%d\n",bin_search1(val));
		else
			printf("%d\n",bin_search2(val));
	}
	
	return 0;
}