#include <fstream>
#include <cstring>
#define M 100001
using namespace std;

ifstream is("cautbin.in");
ofstream os("cautbin.out");

int n, m, a[M], x, op, w;
char s[M];

void Read();
void Bin0();
void Bin1();
void Bin2();

int main()
{
    Read();
    for ( int i = 0; i < m; ++i )
    {
        is >> op >> x;
        switch(op)
        {
            case 0 : Bin0(); break;
            case 1 : Bin1(); break;
            case 2 : Bin2(); break;
        }
    }
    is.close();
    os.close();
    return 0;
}
void Read()
{
    is >> n;
    is.get();
    is.getline( s, M );
    int l = strlen(s);
    for ( int i = 0; i < l; ++i )
    {
        if ( s[i] == ' ' )
            w++;
        else
            a[w] = a[w] * 10 + s[i] - 48;
    }
    is >> m;
}
void Bin0()
{
    int m = 0;
    int st = 0, dr = n-1;
    bool da = false;
    while ( st <= dr )
    {
        m = st + ( dr - st ) / 2;
        if ( a[st] > x )
            break;
        if ( a[m] == x )
        {
            da = true;
            break;
        }
        else if ( a[m] < x )
            st = m+1;
        else
            dr = m-1;
    }
    if ( da )
    {
        while ( a[m+1] == x )
            m++;
        os << m+1 << '\n';
    }
    else
        os << -1 << '\n';

}
void Bin1()
{
    int st = 0, dr = n-1, m = 0;
    bool da = false;
    while ( st <= dr )
    {
        m = st + (dr-st)/2;
        if ( a[m] == x )
        {
            da = true;
            break;
        }
        else if ( a[m] < x )
            st = m+1;
        else
            dr = m-1;
    }
    if ( da )
    {
        while ( a[m+1] == x )
            m++;
        os << m+1 << '\n';
    }
    else
        os << st << '\n';
}
void Bin2()
{
    int st = 0, dr = n-1, m = 0;
    bool da = false;
    while(st<=dr)
    {
        m = st + (dr-st)/2;
        if ( a[m] == x )
        {
            da = true;
            break;
        }
        else if ( a[m] < x )
            st = m+1;
        else
            dr = m-1;
    }
    if ( da )
    {
        while ( a[m-1] == x )
            m--;
        os << m+1 << '\n';
    }
    else
    {
        os << st+1 << '\n';
    }
}