// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef __int128 lll;

const ll inf = 1e18 + 1, mod = 998244353;
const ld eps = 1e-9, pi = acos(-1);
#define all(a) a.begin(), a.end()
#define mpp make_pair
#define F first
#define S second

mt19937_64 rng(234);

ll n;
vector<ll>a;

struct node {
    ll x;
    node *l=nullptr,*r=nullptr;

    node(ll x_) {
        x=x_;
    }
};

pair<vector<ll>,vector<ll>>get() {
    node* nd=new node(0);
    auto bg=nd;
    for (ll i=1;i<n;i++)
        if (a[i]!=a[i-1]) {
            nd->r=new node(i);
            nd->r->l=nd;
            nd=nd->r;
        }
    vector<ll>qu,an(n,-1);
    while (qu.size()<n) {
        ll pr=-1;
        if (!qu.empty())
            pr=a[qu.back()];

        auto it=bg;
        while (it!=nullptr&&a[it->x]==pr) {
            it=it->r;
        }
        if (it==nullptr)
            break;

        ll i0=it->x;

        an[i0]=qu.size();
        qu.push_back(i0);
        if (i0!=n-1&&a[i0]==a[i0+1])
            it->x=i0+1;
        else {
            if (it->l!=nullptr)
                it->l->r=it->r;
            if (it->r!=nullptr)
                it->r->l=it->l;
            if (bg==it)
                bg=it->r;
            delete it;
        }
    }
    while (bg!=nullptr) {
        ll i0=bg->x;
        bg=bg->r;
        if (bg!=nullptr)
            delete bg->l;
        for (ll i=i0;i<n&&an[i]==-1;i++) {
            an[i]=qu.size();
            qu.push_back(i);
        }
    }
    return {an,qu};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll q;cin>>n>>q;
    a.resize(n);
    for (auto &i:a)
        cin>>i;
    auto pp=get();
    auto an=pp.F,qu=pp.S;
    while (q--) {
        ll t,i;cin>>t>>i;
        i--;
        if (t==2) {
            cout<<an[i]+1<<'\n';
            continue;
        }
        if (an[i+1]<an[i]) {
            swap(a[i],a[i+1]);
            swap(an[i],an[i+1]);
            swap(qu[an[i]],qu[an[i+1]]);
            continue;
        }
        if (an[i]&&a[qu[an[i]-1]]==a[i+1]) {
            swap(a[i],a[i+1]);
            swap(an[i],an[i+1]);
            swap(qu[an[i]],qu[an[i+1]]);
            continue;
        }
        if (i>=3) {
            swap(a[i],a[i+1]);
            continue;
        }

        swap(a[i],a[i+1]);
        pp=get();
        an=pp.F,qu=pp.S;
    }
}
