#include <fstream>

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

int caut(int a[], int N, int i, int x);

int main()
{
    int N, a[100000], x, M, instr;
    fin >> N >> M;
    for (int i = 0; i < N; ++i)
        fin >> a[i];
    for (int i = 0; i < M; ++i)
    {
        fin >> instr >> x;
        fout << caut(a, N, instr, x) << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}

int caut(int a[], int N, int i, int x)
{
    int l = 0, r = N - 1, m;
    if  (i == 0)
    {
        int p = -1;
        while (l <= r)
        {
            m = (l + r) / 2;
            if (a[m] == x)
                p = -1;
            if (x < a[m])
                r = m - 1;
            else
                l = m + 1;
        }
    }
    if (i == 1)
    {
        int maxim = -1;
        while (l <= r)
        {
            m = (l + r) / 2;
            if (a[m] == x)
            {
                if (m > maxim)
                    maxim = m;
            }
            if (x > a[m])
                l = m + 1;
            else
                r = m - 1;

        }
        return maxim;
    }
    else
    if (i == 2)
    {
        while (l <= r)
        {
            m = (l + r) / 2;
            if (a[m] >= x)
            {
                return m;
                break;
            }
            if (a[m] < x)
                l = m + 1;
            else
                r = m - 1;

        }
    }
}