#include <bits/stdc++.h>
using namespace std;
const int MX = 2e5 + 5;
int n, q, SZ, Ans = 0, Arr[MX], Answers[MX], last[MX], freq[MX];
struct query{
// t represents how many updates are there before this query
int l, r, t, id;
}Q[MX];
struct update{
int index, pre, now;
}U[MX];
bool cmp(query a, query b){
int l1 = a.l/SZ, l2 = b.l/SZ;
int r1 = a.r/SZ, r2 = b.r/SZ;
if(l1 != l2) return l1 < l2;
if(r1 != r2) return r1 < r2;
return a.t < b.t;
}
void add(int x){
freq[x]++;
if(freq[x] == 1) Ans++;
if(freq[x] == 2) Ans--;
}
void remove(int x){
freq[x]--;
if(freq[x] == 0) Ans--;
if(freq[x] == 1) Ans++;
}
void apply(int x, int val, int l, int r){
if(x >= l && x <= r){
remove(Arr[x]);
Arr[x] = val;
add(Arr[x]);
}else{
Arr[x] = val;
}
}
int main(){
int id, q_id = 0, u_id = 0, l, r, val;
scanf("%d %d", &n, &q);
SZ = sqrt(n);
for(int i = 0; i < n; scanf("%d", &Arr[i]), last[i] = Arr[i], i++);
for(int i = 0; i < q; i++){
scanf("%d", &id);
if(id == 1){
scanf("%d %d", &l, &val);
U[u_id++] = {l, last[l], val};
last[l] = val;
}else{
scanf("%d %d", &l, &r);
Q[q_id].l = l;
Q[q_id].r = r;
Q[q_id].t = u_id;
Q[q_id].id = q_id;
q_id++;
}
}
sort(Q, Q + q_id, cmp);
int mo_left = 0, mo_right = -1, t = 0;
for(int i = 0; i < q_id; i++){
l = Q[i].l, r = Q[i].r;
for(; mo_right < r ; mo_right++, add(Arr[mo_right]));
for(; mo_right > r ; remove(Arr[mo_right]), mo_right--);
for(; mo_left < l ; remove(Arr[mo_left]), mo_left++);
for(; mo_left > l ; mo_left--, add(Arr[mo_left]));
for(; t < Q[i].t ; apply(U[t].index, U[t].now, l, r), t++);
for(; t > Q[i].t ; t--, apply(U[t].index, U[t].pre, l, r));
Answers[Q[i].id] = Ans;
}
for(int i = 0; i < q_id; i++){
printf("%d\n", Answers[i]);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1YID0gMmU1ICsgNTsKaW50IG4sIHEsIFNaLCBBbnMgPSAwLCBBcnJbTVhdLCBBbnN3ZXJzW01YXSwgbGFzdFtNWF0sIGZyZXFbTVhdOwoKc3RydWN0IHF1ZXJ5ewoJLy8gdCByZXByZXNlbnRzIGhvdyBtYW55IHVwZGF0ZXMgYXJlIHRoZXJlIGJlZm9yZSB0aGlzIHF1ZXJ5CglpbnQgbCwgciwgdCwgaWQ7Cn1RW01YXTsKCnN0cnVjdCB1cGRhdGV7CglpbnQgaW5kZXgsIHByZSwgbm93Owp9VVtNWF07Cgpib29sIGNtcChxdWVyeSBhLCBxdWVyeSBiKXsKCWludCBsMSA9IGEubC9TWiwgbDIgPSBiLmwvU1o7CglpbnQgcjEgPSBhLnIvU1osIHIyID0gYi5yL1NaOwoKCWlmKGwxICE9IGwyKSByZXR1cm4gbDEgPCBsMjsKCWlmKHIxICE9IHIyKSByZXR1cm4gcjEgPCByMjsKCXJldHVybiBhLnQgPCBiLnQ7Cn0KCnZvaWQgYWRkKGludCB4KXsKCWZyZXFbeF0rKzsKCWlmKGZyZXFbeF0gPT0gMSkgQW5zKys7CglpZihmcmVxW3hdID09IDIpIEFucy0tOwp9Cgp2b2lkIHJlbW92ZShpbnQgeCl7CglmcmVxW3hdLS07CglpZihmcmVxW3hdID09IDApIEFucy0tOwoJaWYoZnJlcVt4XSA9PSAxKSBBbnMrKzsKfQoKdm9pZCBhcHBseShpbnQgeCwgaW50IHZhbCwgaW50IGwsIGludCByKXsKCWlmKHggPj0gbCAmJiB4IDw9IHIpewoJCXJlbW92ZShBcnJbeF0pOwoJCUFyclt4XSA9IHZhbDsKCQlhZGQoQXJyW3hdKTsKCX1lbHNlewoJCUFyclt4XSA9IHZhbDsKCX0KfQoKaW50IG1haW4oKXsKCWludCBpZCwgcV9pZCA9IDAsIHVfaWQgPSAwLCBsLCByLCB2YWw7CglzY2FuZigiJWQgJWQiLCAmbiwgJnEpOwoJU1ogPSBzcXJ0KG4pOwoJZm9yKGludCBpID0gMDsgaSA8IG47IHNjYW5mKCIlZCIsICZBcnJbaV0pLCBsYXN0W2ldID0gQXJyW2ldLCBpKyspOwoKCWZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspewoJCXNjYW5mKCIlZCIsICZpZCk7CgkJaWYoaWQgPT0gMSl7CgkJCXNjYW5mKCIlZCAlZCIsICZsLCAmdmFsKTsKCQkJVVt1X2lkKytdID0ge2wsIGxhc3RbbF0sIHZhbH07CgkJCWxhc3RbbF0gPSB2YWw7CgkJfWVsc2V7CgkJCXNjYW5mKCIlZCAlZCIsICZsLCAmcik7CgkJCVFbcV9pZF0ubCA9IGw7CgkJCVFbcV9pZF0uciA9IHI7CgkJCVFbcV9pZF0udCA9IHVfaWQ7CgkJCVFbcV9pZF0uaWQgPSBxX2lkOwoJCQlxX2lkKys7CgkJfQoJfQoJCglzb3J0KFEsIFEgKyBxX2lkLCBjbXApOwoJaW50IG1vX2xlZnQgPSAwLCBtb19yaWdodCA9IC0xLCB0ID0gMDsKCglmb3IoaW50IGkgPSAwOyBpIDwgcV9pZDsgaSsrKXsKCQlsID0gUVtpXS5sLCByID0gUVtpXS5yOyAKCQoJCWZvcig7IG1vX3JpZ2h0IDwgciA7IG1vX3JpZ2h0KyssIGFkZChBcnJbbW9fcmlnaHRdKSk7CgkJZm9yKDsgbW9fcmlnaHQgPiByIDsgcmVtb3ZlKEFyclttb19yaWdodF0pLCBtb19yaWdodC0tKTsKCQlmb3IoOyBtb19sZWZ0IDwgbCA7IHJlbW92ZShBcnJbbW9fbGVmdF0pLCBtb19sZWZ0KyspOwoJCWZvcig7IG1vX2xlZnQgPiBsIDsgbW9fbGVmdC0tLCBhZGQoQXJyW21vX2xlZnRdKSk7CgkJCgkJZm9yKDsgdCA8IFFbaV0udCA7IGFwcGx5KFVbdF0uaW5kZXgsIFVbdF0ubm93LCBsLCByKSwgdCsrKTsKCQlmb3IoOyB0ID4gUVtpXS50IDsgdC0tLCBhcHBseShVW3RdLmluZGV4LCBVW3RdLnByZSwgbCwgcikpOwoJICAgICAgICAgICAgCgkJQW5zd2Vyc1tRW2ldLmlkXSA9IEFuczsKCX0KCglmb3IoaW50IGkgPSAwOyBpIDwgcV9pZDsgaSsrKXsKCQlwcmludGYoIiVkXG4iLCBBbnN3ZXJzW2ldKTsKCX0KCgoJcmV0dXJuIDA7Cn0=