## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>

#define int long long

using namespace std;

void maxify(int &a, int b) { b > a && (a = b); }
void minify(int &a, int b) { b < a && (a = b); }

struct IOManager {
template <typename T>
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager operator > (T &x) {
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager operator < (T x) {
write(x); return *this;
}
} io;

struct BinaryIndexedTree {
private:
static const int N = 200000;
int n, a[N];

public:
void init(int t) {
n = t, memset(a, 0, sizeof a);
}
void add(int p, int v) {
for (; p <= n; p += p & -p) a[p] += v;
}
int get(int p) {
int ret = 0;
for (; p; p -= p & -p) ret += a[p];
return ret;
}
};

struct Set {
private:
static const int N = 200000;
int a[N];
set <int> s[N];
set <int> :: iterator it;

public:
void modify(int p, int v) {
if (a[p]) s[a[p]].erase(p);
a[p] = v;
s[a[p]].insert(p);
}
int prev(int p) {
it = s[a[p]].find(p);
return it == s[a[p]].begin() ? *it : *(-- it);
}
int next(int p) {
it = ++ s[a[p]].find(p);
return it == s[a[p]].end() ? *(-- it) : *it;
}
};

#define MODIFY 1
#define QUERY 2

struct Solver {
private:
static const int N = 200000;
int n, m, numq, top, pos[N], pre[N], ans[N];
BinaryIndexedTree tree;
Set s;
struct Query {
int type, x, y, w, id;
bool operator < (const Query &q) const {
return x == q.x ? type < q.type : x < q.x;
}
} q[N << 2], tmp[N << 2];
void add_query(int type, int x, int y, int w, int id) {
q[++ numq] = (Query) { type, x, y, w, id };
}
void input() {
io > n > m;
for (int i = 2; i <= n + 1; ++ i) {
int t; io > t, s.modify(i, t);
int prev = s.prev(i);
add_query(MODIFY, prev, i, i - prev, 0);
}
for (int i = 1; i <= m; ++ i) {
int o; io > o;
if (o == 1) {
int p, x; io > p > x; ++ p;
int prev = s.prev(p), next = s.next(p);
if (prev < p) add_query(MODIFY, prev, p, prev - p, 0);
if (next > p) add_query(MODIFY, p, next, p - next, 0);
if (prev < p && next > p) add_query(MODIFY, prev, next, next - prev, 0);
s.modify(p, x);
prev = s.prev(p), next = s.next(p);
if (prev < p && next > p) add_query(MODIFY, prev, next, prev - next, 0);
if (prev < p) add_query(MODIFY, prev, p, p - prev, 0);
if (next > p) add_query(MODIFY, p, next, next - p, 0);
} else {
int l, r; io > l > r, ++ l, ++ r, ++ top;
add_query(QUERY, r, l - 1, -1, top);
add_query(QUERY, l - 1, r, -1, top);
add_query(QUERY, l - 1, l - 1, 1, top);
}
}
}
void process(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
process(l, mid), process(mid + 1, r);
int s = l, t = mid + 1, pnt = l;
while (s <= mid && t <= r) {
if (q[s] < q[t]) {
if (q[s].type == MODIFY) tree.add(q[s].y, q[s].w);
tmp[pnt ++] = q[s ++];
} else {
if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
tmp[pnt ++] = q[t ++];
}
}
while (t <= r) {
if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
tmp[pnt ++] = q[t ++];
}
for (int i = l; i < s; ++ i) if (q[i].type == MODIFY) tree.add(q[i].y, -q[i].w);
while (s <= mid) tmp[pnt ++] = q[s ++];
for (int i = l; i <= r; ++ i) q[i] = tmp[i];
}

public:
void solve() {
input(), tree.init(n + 1), process(1, numq);
for (int i = 1; i <= top; ++ i) io < ans[i] < '\n';
}
} solver;

signed main() {
solver.solve();
return 0;
}