#include<bits/stdc++.h>
using namespace std;
int n, q;
int a[500005];
int maxa;
void read()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxa = max(a[i], maxa);
    }
}
vector <int> v[500005];
void fill_v()
{
    for(int i = 1; i <= maxa; i++)
        v[i].clear();
    for(int i = n; i >= 2; i--)
    {
        v[a[i]].push_back(i);
    }
}
void type1(int x, int y)
{
    swap(a[x], a[y]);
}
int num[500005];
void type2(int y)
{
    fill_v();
    ///set <int> s;
    priority_queue <int> s;
    for(int i = 1; i <= maxa; i++)
    {
        int c = v[i].size()-1;
        if(c >= 0)
            s.push(-v[i][c]);
    }
    int last = 1;
    num[1] = 1;
    while(!s.empty())
    {
        ///cout << last << " ";
        /*set <int>::iterator it = s.begin();
        int c = *it;*/
        int c = -s.top();
        if(a[c] != a[last])
        {
            num[c] = num[last]+1;
            last = c;
            v[a[c]].pop_back();
            int c1 = v[a[c]].size();
            s.pop();
            if(c1 != 0)
                s.push(-v[a[c]][c1-1]);
        }
        else
        {
            int c2 = c;
            s.pop();
            if(s.empty())
            {
                num[c] = num[last]+1;
                last = c;
                v[a[c]].pop_back();
                int c1 = v[a[c]].size();
                if(c1 != 0)
                    s.push(-v[a[c]][c1-1]);
            }
            else
            {
                c = -s.top();
                num[c] = num[last]+1;
                last = c;
                v[a[c]].pop_back();
                s.pop();
                int c1 = v[a[c]].size();
                if(c1 != 0)
                    s.push(-v[a[c]][c1-1]);
                s.push(-c2);
            }
        }
    }
    ///cout << endl;
    cout << num[y] << endl;
}
void solve()
{
    int t, x;
    int cnt = 0;
    for(int i = 1; i <= q; i++)
    {
        cin >> t >> x;
        if(t == 1){type1(x, x+1); cnt++;}
        else
        {
            if(cnt)
                type2(x);
            else
                cout << num[x] << endl;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    read();
    solve();
    return 0;
}

