/*
 File   : CautareBinara.cpp
 Author : Cristian "Dr.Optix" Dinu
 Purpose: Solution for problem: http://infoarena.ro/problema/cautbin
*/

#include <stdio.h>

//Vars
long N, M, V[100001];
long t, x;
FILE *fin, *fout;

//Prototypes
long SearchType0(long x);
long SearchType1(long x);
long SearchType2(long x);

int main()
{
    //Open files
    fin = fopen("cautbin.in","r");
    fout = fopen("cautbin.out","w");

    //Read the data
    fscanf(fin,"%ld",&N);

    long i;
    for( i=1; i<=N; i++ )
    {
        fscanf(fin,"%ld",&V[i]);
    }

    //Process the questions as we read them
    fscanf(fin,"%ld",&M);

    for( i=1; i<=M; i++ )
    {
        fscanf(fin, "%ld %ld", &t, &x);

        switch(t)
        {
            case 0:
                fprintf(fout,"%ld\n",SearchType0(x));
                break;

            case 1:
                fprintf(fout,"%ld\n",SearchType1(x));
                break;

            case 2:
                fprintf(fout,"%ld\n",SearchType2(x));
                break;
        }
    }

    return 0;
}


long SearchType0(long x)
{
    long mid, low=1, high=N;

    do
    {
        mid = low + (high - low)/2;
        if( x < V[mid] )
        {
            high = mid - 1;
        }
        else if( V[mid] < x)
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
    }while( low<=high );

    return -1;
}

long SearchType1(long x)
{
    long mid, low=1, high=N, last=0;

    do
    {
        mid = low + (high - low)/2;
        if( x >= V[mid] )
        {
            last = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }while( low<=high );

    return last;
}

long SearchType2(long x)
{
    long mid, low=1, high=N, last = N+1;

    do
    {
		mid = low + (high-low) / 2;
		if (x <= V[mid])
		{
		    last = mid;
		    high = mid-1;
		}
		else
		{
		    low = mid+1;
		}
	}while(low<=high);
	return last;

}