#include <iostream.h>
#include <fstream.h>
#define NMAX 100000

int v[NMAX];
fstream f("cautbin.in");
fstream g("cautbin.out");

int c_b1(int x,int a,int b)
{
    int m;

    while (a <= b) {
        m = (a + b) / 2;
        if (v[m] <= x)
            a = m + 1;
        else
            b = m - 1;
    }
    m = (a + b) / 2;

    if (v[m] > x) m --;
    if (v[m] == x)
        return m;
    return -1;
}

int c_b2(int x,int a,int b)
{
    int m;

    while (a < b){
        m = (a + b) / 2;
        if (v[m] <= x)
            a = m + 1;
        else
            b = m;
    }

    m = (a + b) / 2;
    if (v[m] > x)
       -- m;
    return m;
}

int c_b3(int x,int a,int b)
{
	int m;
	while(a<b)
	{
		m=(a+b)/2;
		if(v[m]<x)
			a=m+1;
		else
			b=m;
	}
	
	m=(a+b)/2;
	if(v[m]<x)
		m++;
	return m;
}

int main()
{
	int i,n,m,x,op;
	
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	
	for(i=1;i<=m;i++)
	{
		f>>op>>x;
		if(op==0)
			g<<c_b1(x,1,n)<<"\n";
		if(op==1)
			g<<c_b2(x,1,n)<<"\n";
		if(op==2)
			g<<c_b3(x,1,n)<<"\n";
	}
	return 0;
}