#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")
//#pragma GCC target("avx2")
 
#define deb(x) cout << #x << " = " << x << "\n"
#define all(x) (x).begin(), (x).end()
#define len(x) (ll) x.size()
#define lsb(x) (x) & -(x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define v(x) (ll)(x - 'a')
 
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
 
using namespace std;
using namespace __gnu_pbds;
typedef struct Treap *ptreap;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pld;
typedef pair <ll, ll> pll;
 
template <class T1, class T2 = less <T1>> using pb_heap = __gnu_pbds::priority_queue <T1, T2, binary_heap_tag>;
template <class T1, class T2 = null_type, class T3 = less <T1>> using pb_map = tree <T1, T2, T3, rb_tree_tag, tree_order_statistics_node_update>;
template <class T1, class T2 = null_type, class T3 = hash <T1>> using pb_umap = gp_hash_table <T1, T2, T3>;
template <class T1, class T2, class T3 = hash <T1>> using umap = unordered_map <T1, T2, T3>;
template <class T> using uset = unordered_set <T>;
template <class T> using vec = vector <T>;
 
const ll infll = numeric_limits <ll>::max() >> 1;
const ll inf = numeric_limits <ll>::max() >> 1;
const ll N = 1e5 + 5;
ll n, q;
ll arr[N];
ll lef[N];
ll rig[N];
 
set <ll> ind[N];
 
struct Treap {
    pii key;
    ll pri;
    ll sum;
 
    ptreap l;
    ptreap r;
 
    Treap(ll x, ll y) {
        key = {x, y};
        pri = rand();
    }
};
 
struct Node {
    ll l, r;
    ptreap lef;
    ptreap rig;
} node[N << 2];
 
ll sum(ptreap &t) {
    return t? t->sum: 0;
}
 
void upd(ptreap &t) {
    if(!t) {
        return;
    }
    t->sum = sum(t->l) + sum(t->r) + t->key.yy;
}
 
void inorder(ptreap &t) {
    if(!t) {
        return;
    }
    inorder(t->l);
    cout << " >> " << t->key.xx << " " << t->key.yy << "\n";
    inorder(t->r);
    // upd(t);
}
 
void split(ptreap t, ptreap &l, ptreap &r, pii key) {
    if(!t) {
        l = r = NULL;
    } else if(key <= t->key) {
        split(t->l, l, t->l, key), r = t;
    } else {
        split(t->r, t->r, r, key), l = t;
    }
    upd(t);
}
 
void merge(ptreap &t, ptreap l, ptreap r) {
    if(!l || !r) {
        t = l? l: r;
    } else if(l->pri > r->pri) {
        merge(l->r, l->r, r), t = l;
    } else {
        merge(r->l, l, r->l), t = r;
    }
    upd(t);
}
 
void insert(ptreap &t, ptreap it) {
    if(!t) {
        t = it;
    } else if(it->pri > t->pri) {
        split(t, it->l, it->r, it->key), t = it;
    } else {
        insert(it->key <= t->key? t->l: t->r, it);
    }
    upd(t);
}
 
void erase(ptreap &t, pii key) {
    if(!t) {
        return;
    }
    if(t->key == key) {
        merge(t, t->l, t->r);
    } else {
        erase(key <= t->key? t->l: t->r, key);
    }
    upd(t);
}
 
ll query(ptreap &t, ll l, ll r) {
    pii pl = {l, -inf};
    pii pr = {r, inf};
    ptreap t1, t2, t3;
    split(t, t1, t2, pl);
    split(t2, t2, t3, pr);
    ll res = sum(t2);
    merge(t1, t1, t2);
    merge(t, t1, t3);
    return res;
}
 
void build(ll id, ll l, ll r) {
    node[id].l = l;
    node[id].r = r;
    if(node[id].l == node[id].r) {
        return;
    }
    ll q = l + r >> 1;
    build(l(id), l, q);
    build(r(id), q + 1, r);
}
 
void update(ll id, ll i, ll x, ll type) {
    if(type == 0) {
        pii oldkey = {lef[i], i};
        ptreap it = new Treap(x, i);
        if(oldkey.xx != -1) {
            erase(node[id].lef, oldkey);
        }
        insert(node[id].lef, it);
    } else {
        pii oldkey = {rig[i], i};
        ptreap it = new Treap(x, i);
        if(oldkey.xx != -1) {
            erase(node[id].rig, oldkey);
        }
        insert(node[id].rig, it);
    }
    if(node[id].l == node[id].r) {
        return;
    }
    ll q = node[id].l + node[id].r >> 1;
    if(i <= q) {
        update(l(id), i, x, type);
    } else {
        update(r(id), i, x, type);
    }
}
 
ll query(ll id, ll l, ll r, ll x, ll type) {
    if(node[id].l == l && node[id].r == r) {
        if(type == 0) {
            return query(node[id].lef, -inf, x - 1);
        } else {
            return query(node[id].rig, x + 1, inf);
        }
    }
    ll res = 0;
    ll q = node[id].l + node[id].r >> 1;
    if(l <= q) {
        res += query(l(id), l, min(q, r), x, type);
    }
    if(r > q) {
        res += query(r(id), max(q + 1, l), r, x, type);
    }
    return res;
}
 
void update(ll i, ll x, ll type) {
    update(0, i, x, type);
    if(type == 0) {
        lef[i] = x;
    } else {
        rig[i] = x;
    }
}
 
void insert(ll x, ll i) {
    auto itr = ind[x].lb(i);
    auto itl = prev(itr);
    if(*itl != 0) {
        update(*itl, i, 1);
    }
    if(*itr != n + 1) {
        update(*itr, i, 0);
    }
    update(i, *itl, 0);
    update(i, *itr, 1);
    ind[x].insert(i);
}
 
void erase(ll x, ll i) {
    auto it = ind[x].lb(i);
    auto itl = prev(it);
    auto itr = next(it);
    if(*itl != 0) {
        // update(*itl, *itr, 1);
    }
    if(*itr != n + 1) {
        // update(*itr, *itl, 0);
    }
    ind[x].erase(i);
}
 
void input() {
    cin >> n >> q;
    for(ll i = 0; i <= n + 1; ++i) {
        lef[i] = -1;
        rig[i] = -1;
    }
    for(ll i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    for(ll i = 1; i <= n; ++i) {
        ind[i].insert(0);
        ind[i].insert(n + 1);
    }
}
 
void solve() {
    build(0, 1, n);
    for(ll i = 1; i <= n; ++i) {
        insert(arr[i], i);
    }
    for(ll i = 0; i < 3; ++i) {
        ll t; cin >> t;
        ll x; cin >> x;
        ll y; cin >> y;
        if(t == 1) {
            erase(arr[x], x); arr[x] = y;
            // insert(arr[x], x);
        } else {
            cout << query(0, x, y, y, 1) - query(0, x, y, x, 0) << "\n";
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    input();
    solve();
}