#include <bits/stdc++.h>
#define endl '\n'
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")


using namespace std;

const int MAXN = 5e5;

vector<int>ve[MAXN + 5];
int n, a[MAXN + 5], qu[MAXN + 5], tree[4 * MAXN + 5];

void build(int v, int l, int r)
{
    if(l == r)
    {
        if(ve[l].size() == 0)tree[v] = 1e9;
        else tree[v] = ve[l].back();

        return;
    }

    int mid = (l + r) / 2;

    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);

    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}

void update(int v, int l, int r, int pos, int val)
{
    if(l == r)
    {
        tree[v] = val;
        return;
    }

    int mid = (l + r) / 2;

    if(pos <= mid)update(v * 2, l, mid, pos, val);
    else update(v * 2 + 1, mid + 1, r, pos, val);

    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}

int query(int v, int l, int r, int ql, int qr)
{
    if(ql > qr)return 1e9;
    if(ql > r || l > qr)return 1e9;
    if(ql <= l && r <= qr)return tree[v];

    int mid = (l + r) / 2;

    return min(query(v * 2, l, mid, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}

void solve()
{
    for(int i = n; i > 0; i--)
    {
        ve[a[i]].push_back(i);
    }

    build(1, 1, n);

    int curr = 1, idx = 0;

    while(true)
    {
        //cout << curr << endl;
        idx++; qu[idx] = curr;
        ve[a[curr]].pop_back();

        if(ve[a[curr]].size() == 0)
        {
            update(1, 1, n, a[curr], 1e9);
        }
        else update(1, 1, n, a[curr], ve[a[curr]].back());

        int nxt = min(query(1, 1, n, 1, a[curr] - 1), query(1, 1, n, a[curr] + 1, n));

        if(nxt == 1e9)
        {
            if(ve[a[curr]].size() == 0)
            {
                break;
            }
            else
            {
                curr = ve[a[curr]].back();
            }
        }
        else curr = nxt;
    }
}

signed main()
{
    srand(time(0));
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int q; cin >> n >> q;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    solve();
    //return 0;

    while(q--)
    {
        int type, x; cin >> type >> x;

        if(type == 1)
        {
            swap(a[x], a[x + 1]);
            solve();
        }
        else
        {
            cout << qu[x] << endl;
        }
    }

    //double  x; cin >> x;
    //cout << fixed << setprecision(6) << x << endl;

    return 0;
}

