#include <fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m;
int a[100001];

int Search1(int st, int dr, int x );
int Search2(int st, int dr, int x );
int Search3(int st, int dr, int x );

int main()
{
	fin >> n;
	for( int i = 1; i <= n; ++i )
		fin >> a[i];
	fin >> m;
	int x, y;
	while( m )
	{
		fin >> x >> y;
		if( x == 0 )
			fout << Search1( 1, n, y ) << '\n';
		if( x == 1 )
			fout << Search2( 1, n, y ) << '\n';
		if( x == 2 )
			fout << Search3( 1, n, y ) << '\n';
		--m;
	}
	fin.close();
	fout.close();
	return 0;
}


int Search1(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 Search2(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 Search3(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;
}