#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

void fast_in_out() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(18) << fixed;
#ifdef LOCAL
    freopen("input.txt", "r",stdin);
    freopen("output.txt", "w",stdout);
#endif
}

typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define all(x) (x).begin(), (x).end()
// #define int long long
// using ll = long long;
const int N = 5e5;
int n, q, c[N];
pair<int, int> a[N];
int pos[N];

void solve() {
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    if (true) {
        vector<int> used(n);
        int pos1 = 0, pos2 = 0;
        for (int i = 0; i < n; ++i) {
            a[i].first = 0;
            int ps = i == 0 ? -1 : a[i - 1].first;
            while (true) {
                if (pos1 < n && used[pos1]) {
                    ++pos1;
                    continue;
                }
                if (pos2 < n && used[pos2]) {
                    ++pos2;
                    continue;
                }
                if (pos1 > pos2) {
                    swap(pos1, pos2);
                }
                if (pos1 < n && pos2 < n && c[pos1] == c[pos2]) {
                    ++pos2;
                    continue;
                }
                break;
            }
            if (pos1 < n && c[pos1] != ps) {
                a[i] = {c[pos1], pos1};
                pos[pos1] = i;
                used[pos1] = 1;
                ++pos1;
                continue;
            }
            if (pos2 < n && c[pos2] != ps) {
                a[i] = {c[pos2], pos2};
                pos[pos2] = i;
                used[pos2] = 1;
                ++pos2;
                continue;
            }
            a[i] = {c[pos1], pos1};
            pos[pos1] = i;
            used[pos1] = 1;
            ++pos1;
        }
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        --y;
        if (x == 1) {
            if (c[y] == c[y + 1]) {
                continue;
            }
            int ps1 = pos[y];
            int ps2 = pos[y + 1];
            if (min(ps1, ps2) > 0 && a[min(ps1, ps2) - 1].first == a[max(ps1, ps2)].first) {
                swap(a[ps1].second, a[ps2].second);
                swap(pos[y], pos[y + 1]);
                swap(c[y], c[y + 1]);
                continue;
            }
            swap(a[ps1].first, a[ps2].first);
            swap(c[y], c[y + 1]);
            for (int i = max(ps1, ps2); i + 2 < n; i += 2) {
                int ok = 0;
                if (a[i].first == a[i + 1].first && a[i + 1].first != a[i + 2].first) {
                    swap(a[i + 1], a[i + 2]);
                    swap(pos[a[i + 1].second], pos[a[i + 2].second]);
                    ok = 1;
                } else {
                    if (i == max(ps1, ps2)) {
                        if (a[min(ps1, ps2)].first == a[i + 2].first &&
                            a[i + 1].first != a[i + 2].first &&
                            a[i + 1].second > a[i + 2].second) {
                            swap(a[i + 1], a[i + 2]);
                            swap(pos[a[i + 1].second], pos[a[i + 2].second]);
                            ok = 1;
                        }
                    } else {
                        if (a[i - 1].first == a[i + 2].first &&
                            a[i + 1].first != a[i + 2].first &&
                            a[i + 1].second > a[i + 2].second) {
                            swap(a[i + 1], a[i + 2]);
                            swap(pos[a[i + 1].second], pos[a[i + 2].second]);
                            ok = 1;
                        }
                    }
                }
                if (ok == 0) {
                    break;
                }
            }
        } else {
            cout << pos[y] + 1 << '\n';
        }
    }
}

signed main() {
    fast_in_out();
    int qwe = 1;
    // cin >> qwe;
    while (qwe--) {
        solve();
    }
}
