#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using ll = long long;
using ld = long double;

const int MOD = 998244353;
const int INFi = 1e9;
const ll INF = 1e18;

using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    auto b = a;
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    }
    vector<ordered_set> s(2);
    for (int i = 0; i < q; i++) {
        int type, x;
        cin >> type >> x;
        x--;
        if (type == 1) {
            s[a[x]].erase(s[a[x]].find_by_order(s[a[x]].order_of_key(x)));
            s[a[x + 1]].erase(s[a[x + 1]].find_by_order(s[a[x + 1]].order_of_key(x + 1)));
            swap(a[x], a[x + 1]);
            s[a[x]].insert(x);
            s[a[x + 1]].insert(x + 1);
        } else {
            int len1 = (int)s[0].size();
            int len2 = (int)s[1].size();
            int c1 = s[0].order_of_key(x);
            int c2 = s[1].order_of_key(x);
            if (s[0].find(x) != s[0].end()) {
                cout << c1 + min(c1 - 1, len2) << '\n';
            } else {
                cout << c2 + min(c2 - 1, len1) << '\n';
            }
        }
    }
}
