//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;
//#pragma GCC optimize("O3,Ofast,unroll-loops")
//#pragma GCC target("avx2,avx,bmi")
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// using ordered_set  = tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

struct node {
    int val = INT_MAX, id;
};

struct segtree {
    vector<node> t;

    node merge(node &a, node &b) {
        if (a.val < b.val) return a;
        return b;
    }

    void upd(int v, int tl, int tr, int pos, int x) {
        if (tl + 1 == tr) {
            t[v].val = x;
            t[v].id = tl;
            return;
        }
        if (pos < (tl + tr) / 2) {
            upd(v * 2, tl, (tl + tr) / 2, pos, x);
        } else {
            upd(v * 2 + 1, (tl + tr) / 2, tr, pos, x);
        }
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }

    node get(int v, int tl, int tr, int ql, int qr) {
        if (qr <= tl || tr <= ql) return node();
        if (ql <= tl && tr <= qr) return t[v];
        node L=get(v * 2, tl, (tl + tr) / 2, ql, qr),R=get(v * 2 + 1, (tl + tr) / 2, tr, ql, qr);
        return merge(L, R);
    }
};


struct fenw {
    vector<int>a;
    int n;
    int len(int i) {
        return (i & (-i));
    }
    void add(int pos, int x) {
        for(pos;pos<=n;pos+=len(pos)) a[pos]+=x;
    }
    int get(int pos) {
        int an=0;
        for(pos;pos;pos-=len(pos)) an+=a[pos];
        return an;
    }
};

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //cout<<3;
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    if (n<=10'000 && q<=10'000) {
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        vector<int> st(n + 1, 0);
        deque<pair<int,int>>arr;
        deque<deque<int>>pos(n+1);
        auto calc = [&]() -> void {
            for(int i=1;i<=n;++i) {
                if (i==1 || arr.back().first!=a[i]) arr.emplace_back(a[i],1);
                else arr.back().second++;
                pos[a[i]].push_back(i);
            }
            int cnt=0;
            int lst = 0;
            while(cnt < n) {
                if (arr.size() == 1) {
                    while(!pos[arr[0].first].empty()) {
                        st[pos[arr[0].first].front()]=cnt++;
                        pos[arr[0].first].pop_front();
                    }
                } else {
                    if (arr[0].first != lst) {
                        st[pos[arr[0].first].front()] = cnt++;
                        pos[arr[0].first].pop_front();
                        arr[0].second--;
                        lst=arr[0].first;
                    } else {
                        st[pos[arr[1].first].front()] = cnt++;
                        pos[arr[1].first].pop_front();
                        arr[1].second--;
                        lst=arr[1].first;
                    }
                    if(arr[0].second==0) {
                        arr.pop_front();
                    } else if(arr[1].second==0) {
                        pair<int,int>f=arr[0];
                        arr.pop_front();arr.pop_front();
                        arr.push_front(f);
                    }
                    while(arr.size() > 1 && arr[0].first==arr[1].first) {
                        arr[1].second+=arr[0].second;
                        arr.pop_front();
                    }
                }
            }
            arr={};
        };
//    for (int i = 1; i <= n; ++i) {
//        cout << st[i][0] << ' ' << st[i][1] << ' ' << st[i][2] << '\n';
//    }
//    return 0;
        calc();
        int pw = 1;
        while (q--) {
            int type;
            cin >> type;
            if (type == 1) {
                int p;
                cin >> p;
                swap(a[p], a[p + 1]);
                pw = 0;
            } else {
                int p;
                cin >> p;
                if (!pw) calc();
                pw = 1;
                cout << st[p]+1 << '\n';
            }
            //cout<<"OK"<<endl;
        }
        return 0;
    }
    int c1=0, c2=0;
    vector<int>a(n+1);
    fenw A;
    A.a.resize(n+1,0);
    A.n=n;
    bool al=1;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        if (a[i]>2) al=0;
        if  (a[i]==1) {
            A.add(i,1);
            c1++;
        } else c2++;
    }
    if (al) {
        while(q--) {
            int type; cin >> type;
            int p; cin >> p;
            if (type==1) {
                if (a[p]==1) A.add(p,-1);
                if (a[p+1]==1) A.add(p+1,-1);
                swap(a[p],a[p+1]);
                if (a[p]==1) A.add(p,1);
                if (a[p+1]==1) A.add(p+1,1);
            } else {
                int x = a[p];
                if (x == 1) {
                    int pos = A.get(p);
                    //cout<<pos<<' ';
                    if (pos > c2) {
                        cout << 2 * c2 + (pos - c2) << ' ';
                    } else {
                        cout<<2*pos-1 + (a[1]!=x)<<'\n';
                    }
                } else {
                    int pos = p - A.get(p);
                    //cout<<pos<<' ';
                    if (pos > c1) {
                        cout << 2 * c1 + (pos - c1) << ' ';
                    } else {
                        cout<<2*pos-1 + (a[1]!=x)<<'\n';
                    }
                }
            }
        }
        return 0;
    }
    while(q--) {
        int type; cin >> type;
        int p; cin >> p;
        if (type==1) {
            if (a[p]==1) A.add(p,-1);
            if (a[p+1]==1) A.add(p+1,-1);
            swap(a[p],a[p+1]);
            if (a[p]==1) A.add(p,1);
            if (a[p+1]==1) A.add(p+1,1);
        } else {
            int x = a[p];
            if (x == 1) {
                int cn = A.get(p-1);
                int nn = (p-1) - A.get(p-1);
                int pos=cn+1;
                if (nn <= cn) {
                    int dif = cn - nn;
                    int hr = (n - p) - (A.get(n) - A.get(p));
                    cout << p + min(dif,hr) << '\n';
//                    if (dif <= hr) {
//                        cout << p + hr + 1 << '\n';
//                    } else {
//                        cout << p + hr
//                    }
                } else {
                    cout<<p<<'\n';
                }
            } else {
                int cn = A.get(p-1);
                int nn = (p-1) - A.get(p-1);
                if (nn < cn) {
                    cout << nn*2+2 - (a[1]!=1)<<'\n';
                } else {
                    cout<<p<<'\n';
                }
            }
        }
    }
}



