#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], v1[500005];
bool used[500005];
bool cmp(int x, int y)
{
    return x > y;
}
void fill_v()
{
    for(int i = 1; i <= n; i++)
    {
        if(i != 1)
            v1[a[i]].push_back(i);
        if(used[a[i]] == 0)
        {
            for(int j = 2; j <= n; j++)
            {
                if(a[j] != a[i])
                {
                    v[a[i]].push_back(j);
                }
            }
            used[a[i]] = 1;
        }
    }
    for(int i = 1; i <= maxa; i++)
    {
        sort(v[i].begin(), v[i].end(), cmp);
        sort(v1[i].begin(), v1[i].end(), cmp);
    }
    ///v1[a[1]].pop_back();
    /*for(int i = 1; i <= maxa; i++)
    {
        cout << i << ":" << endl;
        for(int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << " ";
        cout << endl;
        for(int j = 0; j < v1[i].size(); j++)
            cout << v1[i][j] << " ";
        cout << endl;
    }*/
}
int bin_search(int x, int i)
{
    int l = 0, r = v[i].size();
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(v[i][mid] == x)return mid;
        if(v[i][mid] > x)l = mid+1;
        else r = mid-1;
    }
    return r;
}
int bin_search1(int x, int i)
{
    int l = 0, r = v1[i].size();
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(v1[i][mid] == x)return mid;
        if(v1[i][mid] > x)l = mid+1;
        else r = mid-1;
    }
    return r;
}
void type1(int x, int y)
{
    if(a[x] == a[y])return;
    for(int i = 1; i <= maxa; i++)
    {
        if(i != a[x])
        {
            int c = bin_search(x, i);
            v[i][c] = y;
        }
        else
        {
            int c = bin_search1(x, i);
            v1[i][c] = y;
        }
        if(i != a[y])
        {
            int c = bin_search(y, i);
            v[i][c] = x;
        }
        else
        {
            int c = bin_search1(y, i);
            v1[i][c] = x;
        }
    }
}
int num[500005];
vector <int> v2[500005], v3[500005];
void type2(int y)
{
    int last = 1;
    num[1] = 1;
    for(int i = 1; i <= maxa; i++)
    {
        v2[i] = v[i];
        v3[i] = v1[i];
        /*cout << i << ":" << endl;
        for(int j = 0; j < v2[i].size(); j++)
            cout << v2[i][j] << " ";
        cout << endl;
        for(int j = 0; j < v3[i].size(); j++)
            cout << v3[i][j] << " ";
        cout << endl;*/
    }
    while(last != y)
    {
        ///cout << last << " ";
        int c = v2[a[last]].size();
        if(c == 0)
        {
            c = v3[a[last]].size();
            num[v3[a[last]][c-1]] = num[last]+1;
            int l = last;
            last = v3[a[last]][c-1];
            v2[a[v3[a[l]][c-1]]].pop_back();
            v3[a[l]].pop_back();
        }
        else
        {
            num[v2[a[last]][c-1]] = num[last]+1;
            int l = last;
            last = v2[a[l]][c-1];
            v3[a[v2[a[l]][c-1]]].pop_back();
            v2[a[l]].pop_back();
        }
    }
    //cout << endl;
    cout << num[y] << endl;
}
void solve()
{
    int t, x;
    for(int i = 1; i <= q; i++)
    {
        cin >> t >> x;
        if(t == 1)type1(x, x+1);
        else type2(x);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    read();
    fill_v();
    solve();
    return 0;
}

