#include <bits/stdc++.h>
using namespace  std;
#define int long long
const int INF = 1e18;
const int mod = 998244353;
vector <int> give_obr(vector <int> vec) {
    vector <int> ans(vec.size());
    for (int i = 0;i < vec.size();i++) {
        ans[vec[i]] = i;
    }
    return ans;
}
int binpow(int a,int b) {
    if (!b)return 1;
    if (b%2==0) {
        int mid = binpow(a,b/2);
        return (mid * mid) % mod;
    }
    return (a * binpow(a,b-1) )% mod;
}
int give_sum(vector <int> &vec) {
    int n = vec.size();
    int ans = 0;
    for (int i = 0;i < n;i++) {
        ans += binpow(vec[i]+1,i+1);
        if (ans >= mod) {
            ans-=mod;
        }
    }
    return ans;
}
void sub_solve(int n,int q) {
    vector <int> vec(n);
    for (int i =0;i < n;i++) {
        cin >> vec[i];
        vec[i]--;
    }
    int mask = (1<<3);
    vector <int> var_ans(mask);
    vector <int> all_zap(q);
    for (int i = 0;i < q;i++) {
        cin >> all_zap[i];
    }
    for (auto el : all_zap) {
        vector <int> tmp = vec;
        if (el == 2) {
            for (int i = 0;i < n;i++) {
                tmp[i] = n - vec[i] - 1;
            }
        }
        if (el == 1) {
            for (int i = 0;i < n;i++) {
                tmp[i] = vec[n-i-1];
            }
        }
        if (el == 3) {
            for (int i = 0;i < n;i++) {
                tmp[vec[i]] = i;
            }
        }
        vec = tmp;
        cout << give_sum(vec) << " ";

    }
}
const int N = 5001;
vector <int> cnt[N];
int sdvig[N];
signed main() {
    int n,q;
    cin >> n >> q;
    vector <int> vec(n);
    for (int i = 0;i < n;i++) {
        cin >> vec[i];
        vec[i]--;
        cnt[vec[i]].push_back(i);
    }
    vector <int> next(n,-1);
    vector <int> ans(n,0);
    int u = 0;
    set <pair<int,int>> st;
    for (int i = 0;i < n;i++) {
        sdvig[i] = 0;
        if (cnt[i].size() != 0) {
            st.insert({cnt[i].front(),i});
        }
    }
    pair<int,int> value_now = {0,vec[0]};
    st.erase(value_now);
    while (!st.empty()) {
        pair<int,int> u = *st.begin();
        st.erase(st.begin());
        int vnow = u.first;
        int indnow = u.second;
        sdvig[value_now.second]++;
        next[value_now.first] = vnow;
        if (cnt[value_now.second].size() != sdvig[value_now.second]) {
            st.insert({cnt[value_now.second][sdvig[value_now.second]],value_now.second});
        }
        value_now = u;
    }
    int tmp = value_now.second;
    for (int i = sdvig[tmp];i < cnt[tmp].size() - 1;i++) {
        next[cnt[tmp][i]] = cnt[tmp][i+1];
    }
    u = 0;
    int now = 1;
    while (u != -1) {
        ans[u] = now++;
        u = next[u];
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 2) {
            int yi;
            cin >> yi;
            yi--;
            cout << ans[yi] << "\n";
        }else {
            int xi;
            cin >> xi;
            xi--;
            if (vec[xi] == vec[xi+1]) {
                continue;
            }
            swap(vec[xi],vec[xi+1]);
            for (int i = 0;i < n;i++) {
                sdvig[i] = 0;
            }
            for (int i = 0;i < n;i++) {
                if (cnt[i].size() != 0) {
                    st.insert({cnt[i].front(),i});
                }
            }
            pair<int,int> value_now = {0,vec[0]};
            st.erase(value_now);
            while (!st.empty()) {
                pair<int,int> u = *st.begin();
                st.erase(st.begin());
                int vnow = u.first;
                int indnow = u.second;
                sdvig[value_now.second]++;
                next[value_now.first] = vnow;
                if (cnt[value_now.second].size() != sdvig[value_now.second]) {
                    st.insert({cnt[value_now.second][sdvig[value_now.second]],value_now.second});
                }
                value_now = u;
            }
            int tmp = value_now.second;
            for (int i = sdvig[tmp];i < cnt[tmp].size() - 1;i++) {
                next[cnt[tmp][i]] = cnt[tmp][i+1];
            }
            u = 0;
            int now = 1;
            while (u != -1) {
                ans[u] = now++;
                u = next[u];
            }
        }
    }
}