/* Author haleyk10198 */
/* 作者: haleyk10198 */
/* CF handle: haleyk100198*/
#include <bits/stdc++.h>
#define MOD 1000000007
#define LINF (1LL<<60)
#define INF 2147483647
#define PI 3.1415926535897932384626433
#define ll long long
#define pii pair<int,int>
#define mp(x,y) make_pair((x),(y))
#define pb(x) push_back((x))
#define vi vector<int>
#define vvi vector<vi>
#define SQN 317
using namespace std;
string itos(int x){
stringstream ss;
ss << x;
return ss.str();
}
int n, m, a[100010], redT[100010], accT[100010];
set<int> s[100010];
void add(int pos, int v, int *T){
for( ++pos; pos <= n; pos+=pos&-pos)
T[pos] += v;
return;
}
int ask(int pos, int *T){
int ret = 0;
for( ++pos; pos; pos-=pos&-pos)
ret += T[pos];
return ret;
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> a[i], s[a[i]].insert(i);
for(int i = 1; i <= n; i++) s[i].insert(n);
for(int i = 0; i < n; i++){
auto it = s[a[i]].upper_bound(i);
int nxt = *it;
add(i, nxt-i, accT);
add(i, nxt-i, redT);
if(nxt == n)
add(n, i-nxt, redT);
if(--it != s[a[i]].begin()){
--it;
int prv = *it;
add(i, prv-i, redT);
}
}
for(int i = 0; i < m; i++){
int op; cin >> op;
if(op == 1){
int pos, x; cin >> pos >> x;
--pos;
auto it = s[a[pos]].upper_bound(pos);
int nxt = *it;
add(pos, pos-nxt, accT);
add(pos, pos-nxt, redT);
add(nxt, nxt-pos, redT);
--it;
if(it-- != s[a[pos]].begin()){
int prv = *it;
add(prv, prv-pos, accT);
add(prv, nxt-prv, accT);
add(prv, nxt-prv, redT);
add(nxt, prv-nxt, redT);
}
s[a[pos]].erase(pos);
a[pos] = x;
it = s[a[pos]].upper_bound(pos);
nxt = *it;
add(pos, nxt-pos, accT);
add(pos, nxt-pos, redT);
add(nxt, pos-nxt, redT);
if(it != s[a[pos]].begin()){
--it;
int prv = *it;
add(prv, prv-nxt, accT);
add(prv, pos-prv, accT);
add(prv, prv-nxt, redT);
add(nxt, nxt-prv, redT);
add(prv, pos-prv, redT);
add(pos, prv-pos, redT);
}
s[a[pos]].insert(pos);
}
else{
int l, r; cin >> l >> r; --l, --r;
int res = ask(r, accT)-ask(l-1, accT);
res -= ask(r, redT);
cout << res << endl;
}
}
return 0;
}
LyogQXV0aG9yIGhhbGV5azEwMTk4ICovCi8qIOS9nOiAhTogIGhhbGV5azEwMTk4ICovCi8qIENGIGhhbmRsZTogaGFsZXlrMTAwMTk4Ki8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CiNkZWZpbmUgTElORiAoMUxMPDw2MCkKI2RlZmluZSBJTkYgMjE0NzQ4MzY0NwojZGVmaW5lIFBJIDMuMTQxNTkyNjUzNTg5NzkzMjM4NDYyNjQzMwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHBpaSBwYWlyPGludCxpbnQ+CiNkZWZpbmUgbXAoeCx5KSBtYWtlX3BhaXIoKHgpLCh5KSkKI2RlZmluZSBwYih4KSBwdXNoX2JhY2soKHgpKQojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdnZpIHZlY3Rvcjx2aT4KI2RlZmluZSBTUU4gMzE3Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RyaW5nIGl0b3MoaW50IHgpewoJc3RyaW5nc3RyZWFtIHNzOwoJc3MgPDwgeDsKCXJldHVybiBzcy5zdHIoKTsKfQoKaW50IG4sIG0sIGFbMTAwMDEwXSwgcmVkVFsxMDAwMTBdLCBhY2NUWzEwMDAxMF07CgpzZXQ8aW50PiBzWzEwMDAxMF07Cgp2b2lkIGFkZChpbnQgcG9zLCBpbnQgdiwgaW50ICpUKXsKCWZvciggKytwb3M7IHBvcyA8PSBuOyBwb3MrPXBvcyYtcG9zKQoJCVRbcG9zXSArPSB2OwoJcmV0dXJuOwp9CgppbnQgYXNrKGludCBwb3MsIGludCAqVCl7CglpbnQgcmV0ID0gMDsKCWZvciggKytwb3M7IHBvczsgcG9zLT1wb3MmLXBvcykKCQlyZXQgKz0gVFtwb3NdOwoJcmV0dXJuIHJldDsKfQoKaW50IG1haW4oKXsKCS8vZnJlb3BlbigiaW5wdXQudHh0IiwiciIsc3RkaW4pOwoJLy9mcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJY2luID4+IG4gPj4gbTsKCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJY2luID4+IGFbaV0sIHNbYVtpXV0uaW5zZXJ0KGkpOwoJZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHNbaV0uaW5zZXJ0KG4pOwoJCglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKCQlhdXRvIGl0ID0gc1thW2ldXS51cHBlcl9ib3VuZChpKTsKCQlpbnQgbnh0ID0gKml0OwoJCWFkZChpLCBueHQtaSwgYWNjVCk7CgkJYWRkKGksIG54dC1pLCByZWRUKTsKCQlpZihueHQgPT0gbikKCQkJYWRkKG4sIGktbnh0LCByZWRUKTsKCQlpZigtLWl0ICE9IHNbYVtpXV0uYmVnaW4oKSl7CgkJCS0taXQ7CgkJCWludCBwcnYgPSAqaXQ7CgkJCWFkZChpLCBwcnYtaSwgcmVkVCk7CgkJfQoJfQoJCglmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKCQlpbnQgb3A7IGNpbiA+PiBvcDsKCQlpZihvcCA9PSAxKXsKCQkJaW50IHBvcywgeDsgY2luID4+IHBvcyA+PiB4OwoJCQktLXBvczsKCQkJCgkJCWF1dG8gaXQgPSBzW2FbcG9zXV0udXBwZXJfYm91bmQocG9zKTsKCQkJaW50IG54dCA9ICppdDsKCQkJYWRkKHBvcywgcG9zLW54dCwgYWNjVCk7CgkJCWFkZChwb3MsIHBvcy1ueHQsIHJlZFQpOwoJCQlhZGQobnh0LCBueHQtcG9zLCByZWRUKTsKCQkJLS1pdDsKCQkJaWYoaXQtLSAhPSBzW2FbcG9zXV0uYmVnaW4oKSl7CgkJCQlpbnQgcHJ2ID0gKml0OwoJCQkJYWRkKHBydiwgcHJ2LXBvcywgYWNjVCk7CgkJCQlhZGQocHJ2LCBueHQtcHJ2LCBhY2NUKTsKCQkJCWFkZChwcnYsIG54dC1wcnYsIHJlZFQpOwoJCQkJYWRkKG54dCwgcHJ2LW54dCwgcmVkVCk7CgkJCX0KCQkJc1thW3Bvc11dLmVyYXNlKHBvcyk7CgkJCQoJCQlhW3Bvc10gPSB4OwoJCQlpdCA9IHNbYVtwb3NdXS51cHBlcl9ib3VuZChwb3MpOwoJCQlueHQgPSAqaXQ7CgkJCWFkZChwb3MsIG54dC1wb3MsIGFjY1QpOwoJCQlhZGQocG9zLCBueHQtcG9zLCByZWRUKTsKCQkJYWRkKG54dCwgcG9zLW54dCwgcmVkVCk7CgkJCWlmKGl0ICE9IHNbYVtwb3NdXS5iZWdpbigpKXsKCQkJCS0taXQ7CgkJCQlpbnQgcHJ2ID0gKml0OwoJCQkJYWRkKHBydiwgcHJ2LW54dCwgYWNjVCk7CgkJCQlhZGQocHJ2LCBwb3MtcHJ2LCBhY2NUKTsKCQkJCgkJCQlhZGQocHJ2LCBwcnYtbnh0LCByZWRUKTsKCQkJCWFkZChueHQsIG54dC1wcnYsIHJlZFQpOwoJCQkJYWRkKHBydiwgcG9zLXBydiwgcmVkVCk7CgkJCQlhZGQocG9zLCBwcnYtcG9zLCByZWRUKTsKCQkJfQoJCQlzW2FbcG9zXV0uaW5zZXJ0KHBvcyk7CgkJfQoJCWVsc2V7CgkJCWludCBsLCByOyBjaW4gPj4gbCA+PiByOyAtLWwsIC0tcjsKCQkJaW50IHJlcyA9IGFzayhyLCBhY2NUKS1hc2sobC0xLCBhY2NUKTsKCQkJcmVzIC09IGFzayhyLCByZWRUKTsKCQkJY291dCA8PCByZXMgPDwgZW5kbDsKCQl9Cgl9CglyZXR1cm4gMDsKfQo=