#include<fstream>
#define N 100010
using namespace std;
int a[N];
int m,i,x,n,y;
int bsearch0 (int st, int dr, int x) 
{
    int mij;

    while (st <= dr) 
	{
        mij = (st + dr) / 2;
        if (a[mij] <= x)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    mij = (st + dr) / 2;

    if (a[mij] > x)
    		mij --;
    if (a[mij] == x)
        return mij;
    return -1;
}

int bsearch1 (int st, int dr, int x)
{
    int mij, n = dr;

    while (st < dr)
	{
        mij = (st + dr) / 2;
        if (a[mij] <= x)
            st = mij + 1;
        else
            dr = mij;
    }

    mij = (st + dr) / 2;
    if (a[mij] > x)
       -- mij;
    return mij;
}

int bsearch2 (int st, int dr, int x) 
{
    int mij;

    while (st < dr) 
	{
        mij = (st + dr) / 2;
        if (a[mij] <x)
            st = mij + 1;
        else
            dr = mij;
    }
    
    mij = (st + dr) / 2;
    if (a[mij] < x)
       ++ mij;
    return mij;
}

int main ()
{
ifstream f("cautbin.in");
ofstream g("cautbin.out");
f>>n;
for(i=1;i<=n;i++)
	f>>a[i];
f>>m;
for(i=1;i<=m;i++)
{
	f>>y>>x;
	if(y==0)
		g<<bsearch0(1,n,x)<<"\n";
	else
		if(y==1)
			g<<bsearch1(1,n,x)<<"\n";
		else
			if(y==2)
				g<<bsearch2(1,n,x)<<"\n";
}
return 0;
}