/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on April 28, 2010, 8:31 PM
 */
#include <cstdlib>
#include <fstream>
#define Nmax 100011

/*
 * 
 */
using namespace std;
int v[Nmax];
int main(int argc, char** argv)
{
    int N, M, x, y, z, left, right, middle;
    ifstream in( "cautbin.in" );
    for( in>>N, x=1; x <= N; ++x )
    {
        in>>v[x];
    }
    ofstream out( "cautbin.out" );
    for( in>>M; M; --M )
    {
        in>>x>>y;
        z=-1;
        left=1; right=N;
        if( !x )
        {
            while( left <= right )
            {
                middle=left+(right-left)/2;
                if( y == v[middle] )
                {
                    for( z=middle; y == v[z+1]; ++z );
                    break;
                }
                if( y > v[middle] )
                    left=middle+1;
                else right=middle-1;
            }
        }
        else if( 1 == x )
             {
                while( left <= right )
                {
                    middle=left+(right-left)/2;
                    if( y >= v[middle] )
                    {
                        z=middle;
                        left=middle+1;
                    }
                    else right=middle-1;
                }
             }
             else {
                        while( left <= right )
                        {
                            middle=left+(right-left)/2;
                            if( y <= v[middle] )
                            {
                                z=middle;
                                right=middle-1;
                            }
                            else left=middle+1;
                        }
                }
        out<<z<<'\n';
    }
    return (EXIT_SUCCESS);
}