/* 
 * File:   main.cpp
 * Author: VirtualDemon
 *
 * Created on April 9, 2010, 11:39 AM
 */
#include <cstdlib>
#include <fstream>
#define Nmax 100001

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