#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001;
int tot, n, m, a[maxn];
struct BIT {
  long long c[maxn];
  void add(int x, int y) {
    while (x <= n) c[x] += y, x += x & -x;
  }
  long long sum(int x) {
    long long ans = 0;
    while (x) ans += c[x], x -= x & -x;
    return ans;
  }
} T;
set<int> s[maxn];
struct req {
  int op, x, y, val;
  friend bool operator<(req a, req b) {
    return a.x != b.x ? a.x > b.x : a.op < b.op;
  }
} q[maxn << 3], h[maxn << 3];
void modify(int x, int y) {
  int old = a[x];
  a[x] = y;
  set<int>::iterator it, l, r;
  it = s[old].lower_bound(x);
  l = r = it;
  --l, ++r;
  q[++tot] = (req){0, *l, x, (*l) - x};
  q[++tot] = (req){0, x, *r, x - (*r)};
  q[++tot] = (req){0, *l, *r, (*r) - (*l)};
  s[old].erase(it);
  s[y].insert(x);
  it = s[y].lower_bound(x);
  l = r = it;
  --l, ++r;
  q[++tot] = (req){0, *l, x, x - (*l)};
  q[++tot] = (req){0, x, *r, (*r) - x};
  q[++tot] = (req){0, *l, *r, (*l) - (*r)};
}
int isq[maxn];
void query(int i, int l, int r) {
  isq[i] = 1;
  q[++tot] = {i, l, r, 0};
}
long long ans[maxn];
void solve(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  for (int k = l, i = l, j = mid + 1; k <= r; k++) {
    if (i > mid || (j <= r && q[j] < q[i])) {
      h[k] = q[j];
      if (q[j].op) ans[q[j].op] += T.sum(q[j].y);
      j++;
    } else {
      h[k] = q[i];
      if (!q[i].op) T.add(q[i].y, q[i].val);
      i++;
    }
  }
  for (int i = l; i <= mid; i++)
    if (!q[i].op) T.add(q[i].y, -q[i].val);
  for (int i = l; i <= r; i++) q[i] = h[i];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) s[i].insert(0), s[i].insert(n + 1);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    s[a[i]].insert(i);
    set<int>::iterator la = --s[a[i]].lower_bound(i);
    q[++tot] = (req){0, *la, i, i - (*la)};
  }
  for (int i = 1; i <= m; i++) {
    int op, a, b;
    scanf("%d%d%d", &op, &a, &b);
    if (op == 1)
      modify(a, b);
    else
      query(i, a, b);
  }
  solve(1, tot);
  for (int i = 1; i <= m; i++)
    if (isq[i]) printf("%lld\n", ans[i]);
}
