#include <iostream>
#include <fstream>

using namespace std;

int n, m, v[100005];


int bsearch0 ( int numar ) {
    int st = 1;
    int dr = n ;

    while ( st <= dr ) {
        int m = ( st + dr ) / 2;
        if ( v[m] <= numar ) {
            st = m + 1;
        }
        else {
            dr = m - 1;
        }
    }

    m = ( st + dr ) / 2;
    if ( v[m] > numar ) --m;
    if ( v[m] == numar ) return m;
    return -1;
}

int bsearch1 ( int numar ) {
    int st = 1;
    int dr = n;

    while ( st < dr ) {
        int m = ( st + dr ) / 2;
        if ( v[m] <= numar ) {
            st = m + 1;
        }
        else {
            dr = m;
        }
    }

    m = ( st + dr ) / 2;
    if ( v[m] > numar ) --m;
    return m;

}

int bsearch2 ( int numar ) {
    int st = 1;
    int dr = n;

    while ( st < dr ) {
        m = ( st + dr ) / 2;
        if ( v[m] >= numar ) {
            dr = m;
        }
        else {
            st = m + 1;
        }
    }

    m = ( st + dr ) / 2;
    if ( v[m] < numar ) ++m;
    return m;
}

int main () {
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");

    f >> n >> m;

    int i, x;
    for ( i = 1; i <= n; ++i ) {
        f >> v[i];
    }

    int intrebare, numar;
    for ( i = 1; i <= m; ++i ) {
        f >> intrebare >> numar;

        if ( intrebare == 0 ) {
            g << bsearch0( numar ) << "\n";
        }
        else {
            if ( intrebare == 1 ) {
                g << bsearch1( numar ) << "\n";
            }
            else {
                g << bsearch2( numar ) << "\n";
            }
        }
    }

    return 0;
}