#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <random>
#include <ctime>
#include <iomanip>
#include <immintrin.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define eb emplace_back
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = long double;
mt19937 rnd(234672);
struct ST {
    int n;
    vector<int>t;
    ST() {
        n = 0;
    }
    ST (int _n) {
        n = _n;
        t.assign(n * 4, 0);
    }
    ST resize(int _n) {
        n = _n;
        t.assign(n * 4, 0);
        return 0;
    }
    void build(int i, int l, int r, vector<int>& a) {
        if (r >= l) return;
        if (l + 1 == r) {
            t[i] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(2 * i + 1, l, m, a);
        build(2 * i + 2, m, r, a);
        t[i] = max(t[2 * i + 1], t[2 * i + 2]);
    }
    void build(vector<int>& a) {
        return build(0, 0, n, a);
    }
    int query(int i, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) return -1;
        if (ql <= l && r <= qr) {
            return t[i];
        }
        int m = (l + r) / 2;
        return max(query(2 * i + 1, l, m, ql, qr), query(2 * i + 2, m, r, ql, qr));
    }
    int query(int l, int r) {
        return query(0, 0, n, l, r);
    }
    void upd(int i, int l, int r, int qi, int x) {
        if (qi < l || qi >= r) return;
        if (l + 1 == r) {
            t[i] = x;
            return;
        }
        int m = (l + r) / 2;
        upd(2 * i + 1, l, m, qi, x);
        upd(2 * i + 2, m, r, qi, x);
        t[i] = max(t[2 * i + 1], t[2 * i + 2]);
    }
    void upd(int i, int x) {
        return upd(0, 0, n, i, x);
    }
};
struct Sparse {
    int n;
    vector<int>t;
    vector<int>l2;
    vector<vector<int>>d;
    Sparse () {
        n = 0;
    }
    Sparse(int _n) {
        n = _n;
        t.resize(n, 0);
        l2.resize(n + 1);
        for (int i = 2; i <= n; ++i) {
            l2[i] = l2[i / 2] + 1;
        }
    }
    void resize(int _n) {
        n = _n;
        t.resize(n, 0);
        l2.resize(n + 1);
        for (int i = 2; i <= n; ++i) {
            l2[i] = l2[i / 2] + 1;
        }
    }
    Sparse(vector<int> a) {
        n = a.size();
        t = a;
        l2.resize(n + 1);
        for (int i = 2; i <= n; ++i) {
            l2[i] = l2[i / 2] + 1;
        }
        d.assign(n, vector<int>(l2[n] + 1));
        for (int i = 0; i < n; ++i) {
            d[i][0] = t[i];
        }
        for (int j = 1; j <= l2[n]; ++j) {
            for (int i = 0; i < n; ++i) {
                if (i + (1 << j) <= n) {
                    d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
                }
            }
        }
    }
    void create(vector<int> a) {
        n = a.size();
        t = a;
        l2.resize(n + 1);
        for (int i = 2; i <= n; ++i) {
            l2[i] = l2[i / 2] + 1;
        }
        d.assign(n, vector<int>(l2[n] + 1));
        for (int i = 0; i < n; ++i) {
            d[i][0] = t[i];
        }
        for (int j = 1; j <= l2[n]; ++j) {
            for (int i = 0; i < n; ++i) {
                if (i + (1 << j) <= n) {
                    d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
                }
            }
        }
    }
    void build() {
        for (int i = 2; i <= n; ++i) {
            l2[i] = l2[i / 2] + 1;
        }
        for (int i = 0; i < n; ++i) {
            d[i][0] = t[i];
        }
        for (int j = 1; j <= l2[n]; ++j) {
            for (int i = 0; i < n; ++i) {
                if (i + (1 << j) <= n) {
                    d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
                }
            }
        }
    }
    int query(int l, int r) {
        int k = l2[r - l];
        return max(d[l][k], d[r - (1 << k)][k]);
    }
};
struct Fenwik {
    int n;
    vector<int>t;
    Fenwik() {
        n = 0;
    }
    Fenwik(int _n) {
        n = _n;
        t.assign(n + 1, 0);
    }
    void add(int i, int x) {
        for (i++; i <= n; i += i & (-i)) {
            t[i] += x;
        }
    }
    int sum(int i) {/// half-intervale[0, i)
        int ans = 0;
        for (; i > 0; i -= i & (-i)) {
            ans += t[i];
        }
        return ans;
    }
    int sum(int l, int r) {/// half-intervale[l, r)
        return sum(r) - sum(l);
    }
};

struct DSU {
    int n;
    vector<int>p;
    bool fuse = true;
    DSU(){n=0;}
    DSU(int _n) {
        n = _n;
        p.resize(n);
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }
    int get(int i) {
        if (p[i] == i) return i;
        else if (fuse) return p[i] = get(p[i]);
        else return get(p[i]);
    }

    int unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (rnd() % 2) swap(x, y);
        p[x] = y;
        return get(y);
    }
};

const int B = 502;
struct Query {
    int i, l, r, ans;
};
bool operator <(const Query& a, const Query& b) {
    if (a.l / B != b.l / B) return a.l < b.l;
    return a.r < b.r;
}
void solve();
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*const int MAX_N = 100002, MAX_M = 100002;
vector<vector<int>>g;
int vis[MAX_N];
void dfs(int u) {
    vis[u] = 1;
    for (auto v : g[u]) {
        if
    }
}
void solve() {
    int n, m;
    cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(0);
}
*/

const ll mod = 998244353;
ll binpow(ll a, ll n) {
    if (n == 0) return 1;
    if (n & 1) return a * binpow(a, n - 1) % mod;
    ll x = binpow(a, n >> 1);
    return x * x % mod;
}
int p[1000002];
int a[1000002];
int x[1000002];
int pos[1000002];
vector<vector<int>>v;
vector<int>prv;
vector<int>compute(int n) {
    /*for (int i = 0; i < n; ++i) {
        cout << i + 1 << ": ";
        for (auto x : v[i]) {
            cout << x << ' ';
        }
        cout << endl;
    }
    for (int i = 0; i < n; ++i) cout << a[i] << ' ';
    cout << endl;
    for (int i = 0; i < n; ++i) cout << pos[i] << ' ';
    cout << endl;
    cout << endl;*/
    int col = -1;
    set<int>S;
    vector<int>ans;
    for (int i = 0; i < n; ++i) {
        if (!v[i].empty()) {
            S.insert(v[i][0]);
        }
    }
    //return {};
    while (!S.empty()) {
        //cout << col << "!" << endl;
        if (S.size() == 1) {
            int tmp = *S.begin();
            ans.push_back(tmp);
            S.erase(S.begin());
            //exit(0);
            //continue;
            if (pos[tmp] + 1 < v[a[tmp]].size()) S.insert(v[a[tmp]][pos[tmp] + 1]);
            //exit(0);
        }
        else {
            //cout << "HERE" << endl;
            int imp = -1;
            if (a[*S.begin()] == col) {
                imp = *S.begin();
                S.erase(S.begin());
            }
            //continue;
            int tmp = *S.begin();
            col = a[tmp];
            ans.push_back(tmp);
            S.erase(S.begin());
            //continue;
            //cout << tmp << "?" << endl;
            if (pos[tmp] + 1 < v[a[tmp]].size()) {
                //cout << "!!!" << v[a[tmp]][pos[tmp] + 1] << endl;
                S.insert(v[a[tmp]][pos[tmp] + 1]);
            }
            if (imp != -1) {
                S.insert(imp);
            }
            //cout << "DONE" << endl;
        }
    }
    vector<int>y(n);
    for (int i = 0; i < n; ++i) {
        y[ans[i]] = i;
        //cout << ans[i] << ' ';
    }
    /*cout << endl;
    for (int i = 0; i < n; ++i) {
        cout << y[i] << ' ';
    }
    cout << endl;
    cout << endl;*/
    if (prv.size()) {
        int dif = 0;
        for (int i = 0; i < n; ++i) {
            if (y[i] != prv[i]) {
                dif++;
            }
        }
        /*for (auto x : y) cout << "!" << x;
        cout << endl;
        for (auto x : prv) cout << "!" << x;
        cout << endl;*/
    }
    prv = y;
    return y;
}
void solve() {
    int n, m;
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i]--;
        pos[i] = v[a[i]].size();
        v[a[i]].push_back(i);
    }
    auto y = compute(n);
    /*for (auto x : y) {
        cout << x + 1 << ' ';
    }
    cout << endl;*/
    //return ;
    for (int i = 0; i < m; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            cin >> x[i];
            x[i]--;
            if (a[x[i]] == a[x[i] + 1]) continue;
            v[a[x[i]]][pos[x[i]]]++;
            v[a[x[i] + 1]][pos[x[i] + 1]]--;
            swap(pos[x[i]], pos[x[i] + 1]);
            swap(a[x[i]], a[x[i] + 1]);
            //cout << "SWAP " << t << ' ' << x[i] << endl;
        }
        else {
            cin >> x[i];
            x[i]--;
            if (pos[x[i]] > v[1 - a[x[i]]].size()) {
                cout << v[1 - a[x[i]]].size() + pos[x[i]] + 1 << '\n';
            }
            else if (a[x[i]] == a[0]) {
                cout << pos[x[i]] * 2 + 1 << '\n';
            }
            else {
                cout << pos[x[i]] * 2 + 2 << '\n';
            }
            //cout << "COUNT " << t << ' ' << x[i] << endl;
            //cout << compute(n)[x[i]] + 1 << '\n';
        }
    }
}
