#include <cstdio>

FILE *in,*out;

const int L = 16;

int v[100001];

int cauta1(int x,int n)
{
		int pas,r = 0;
		pas = 1 << L;
		while(pas != 0)
		{
				if(v[r + pas] == x && r + pas <= n)
					r += pas;
				pas /= 2;
		}
		if(r == 0)
			r = -1;
		return r;
}
int cauta2(int x,int n)
{
		int pas,r = 0;
		pas = 1 << L;
		while(pas != 0)
		{
				if(v[r + pas] <= x && r + pas <= n)
					r += pas;
				pas /= 2;
		}
		return r;
}

int cauta3(int x,int n)
{
		int pas,r = 0;
		pas = 1 << L;
		while(pas != 0)
		{
			if(v[r + pas] < x && r + pas <= n)
			{
					r += pas;
			}
			pas /= 2;
		}
		return r+1;
}

using namespace std;

int main()
{
		in = fopen("cautbin.in","r");
		out = fopen("cautbin.out","w");
		int n,m,intrebare,x;
		fscanf(in,"%d",&n);
		for(int i = 1;i <= n;i ++)
			fscanf(in,"%d",&v[i]);
		fscanf(in,"%d",&m);
		for(int i = 1;i <= m;i ++)
		{
			fscanf(in,"%d %d",&intrebare,&x);
			if(intrebare == 0)
				fprintf(out,"%d\n",cauta1(x,n));
			if(intrebare == 1)
				fprintf(out,"%d\n",cauta2(x,n));
			if(intrebare == 2)
				fprintf(out,"%d\n",cauta3(x,n));
		}

    return 0;
}