#include<bits/stdc++.h>
#define int long long
#define f(i , l , r) for(int i = (l);i <= (r);i ++)
#define d(i , l , r) for(int i = (r);i >= (l);i --)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define sc second
#define lowbit(x) ((x)&-(x))
#define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
const int N = 1e5 + 10 , M = 1e6 + 10;
int root[M] , res , n , q;
struct node{
    int l , r , vall , valr , sum;
}tree[N*60];
int st[N*60] , h;
void make(int &u){if(!u)u = (h ? st[h--] : ++res);}
void clear(int u){st[++h] = u , tree[u] = {0 , 0 , 0 , 0 , 0};}
void up(int u){
    tree[u].sum = tree[tree[u].l].sum + tree[tree[u].r].sum - (tree[tree[u].r].vall&&tree[tree[u].l].valr&&abs(tree[tree[u].r].vall - tree[tree[u].l].valr) == 1);
    tree[u].vall = (tree[tree[u].l].vall ? tree[tree[u].l].vall : tree[tree[u].r].vall);
    tree[u].valr = (tree[tree[u].r].valr ? tree[tree[u].r].valr : tree[tree[u].l].valr);
}
void input(int &u,int l,int r,int p){
    make(u);
    if(l == p&&r == p)return tree[u] = {0 , 0 , p , p , 1} , void();
    int mid = l + r >> 1;
    if(p <= mid)input(tree[u].l , l , mid , p);
    if(p > mid)input(tree[u].r , mid + 1 , r , p);
    up(u);
    // printf("[%lld , %lld] = {%lld , %lld , %lld}\n" , l , r , tree[u].vall , tree[u].valr , tree[u].sum);
    return ;
}
int merge(int x,int y,int l,int r){
    int u = 0;make(u);
    if(!x||!y)return tree[u] = tree[x+y] , u;
    if(l == r)return tree[u] = {0 , 0 , l , l , 1} , clear(x) , clear(y) , u;
    int mid = l + r >> 1;
    tree[u].l = merge(tree[x].l , tree[y].l , l , mid);
    tree[u].r = merge(tree[x].r , tree[y].r , mid + 1 , r);
    return clear(x) , clear(y) , up(u) , u;
}
void work(){
    cin >> n >> q;
    f(i , 1 , n){
        int c;
        cin >> c;
        input(root[c] , 1 , n , i);
    }
    int ans = 0;
    f(i , 1 , 1000000)ans += tree[root[i]].sum;
    f(i , 1 , q){
        int op;cin >> op;
        if(op == 1){
            int u ,v;
            cin >> u >> v;
            if(u == v)continue ;
            ans -= tree[root[u]].sum , ans -= tree[root[v]].sum;
            root[v] = merge(root[u] , root[v] , 1 , n) , root[u] = 0;
            ans += tree[root[v]].sum;
            cout << "1 " << u << " " << v << "\n";
        }
        else cout << ans << "\n";
    }
}
signed main(){
    int T = 1;
    while(T --)work();
}