#include <iostream>
#include <fstream>

using namespace std;

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

int n , A [100001] , m ;
void Citire()
{
    int i ;
    fin >> n;
    for ( i = 1 ; i <= n ; ++ i )
          fin >> A[i];
    fin >> m ;
}

int CautareBinara ( int n , int A[] , int val )
{
    int i , step ;

    for ( step = 1 ; step < n ;step <<= 1 ) ;

    for ( i = 0 ; step ; step >>= 1 )
       if ( i + step <= n && A [i+step] <= val )
             i += step ;

    // if ( A [i] == val )
        return i ;
    //else
      //  return - 1 ;
}

void Rezolvare ()
{
    int x1 , x2 ;
    while ( m >= 1 )
    {
        fin >> x1 >> x2 ;
        switch (x1)
        {
            case 0 : fout << ( ( A [ (x1 = CautareBinara ( n , A , x2 ) )] == x2 ) ? x1 : -1 ) << "\n" ; break ;
            case 1 : fout << CautareBinara ( n , A , x2 ) << "\n" ; break ;
            case 2 : fout << ( CautareBinara ( n , A , -- x2 ) + 1 )  << "\n" ; break ;
        }
     -- m ;
    }
}
int main()
{
    Citire();
    Rezolvare() ;

    return 0;
}