#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int a[N], n, Q, res[N];
long long ans[N], c[N];
set<int> st[N];
struct node {
  int op, x, y, id, pre;
  node() {}
  node(int op, int x, int y, int id, int pre)
      : op(op), x(x), y(y), id(id), pre(pre) {}
} q[N << 3];
int main() {
  auto lowbit = [&](int x) { return x & -x; };
  auto update = [&](int x, int val) {
    for (; x <= n; x += lowbit(x)) c[x] += val;
  };
  auto get_sum = [&](int x) {
    long long ans = 0;
    for (; x; x -= lowbit(x)) ans += c[x];
    return ans;
  };
  function<void(int, int)> solve = [&](int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    solve(l, mid);
    solve(mid + 1, r);
    sort(q + l, q + mid + 1,
         [](const node &a, const node &b) { return a.x < b.x; });
    sort(q + mid + 1, q + r + 1,
         [](const node &a, const node &b) { return a.y < b.y; });
    int pos = l;
    for (int i = mid + 1; i <= r; i++) {
      if (q[i].op == 1) continue;
      for (; pos <= mid; pos++) {
        if (q[pos].op == 2) continue;
        if (q[pos].x > q[i].y) break;
        update(q[pos].pre, q[pos].y);
      }
      ans[q[i].id] += get_sum(q[i].y) - get_sum(q[i].x - 1);
    }
    for (int i = l; i < pos; i++)
      if (q[i].op == 1) update(q[i].pre, -q[i].y);
    return;
  };
  scanf("%d %d", &n, &Q);
  int tot = 0, id = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    int val, pre;
    if (st[a[i]].empty())
      val = 0, pre = n + 1;
    else {
      pre = *(--st[a[i]].end());
      val = i - pre;
    }
    st[a[i]].insert(i);
    q[++tot] = node(1, i, res[i] = val, id, pre);
  }
  for (int i = 1; i <= Q; i++) {
    int op, x, y;
    scanf("%d %d %d", &op, &x, &y);
    if (op == 1) {
      st[a[x]].erase(x);
      int L = 0, R = 0;
      auto it = st[a[x]].lower_bound(x);
      if (it != st[a[x]].end()) R = *it, q[++tot] = node(1, R, -res[R], id, x);
      if (it != st[a[x]].begin())
        L = *(--it), q[++tot] = node(1, x, -res[x], id, L);
      res[R] = res[x] = 0;
      if (L && R) q[++tot] = node(1, R, res[R] = R - L, id, L);
      a[x] = y;
      it = st[a[x]].lower_bound(x);
      L = R = 0;
      if (it != st[a[x]].end())
        R = *it, q[++tot] = node(1, R, res[R] = R - x, id, x);
      if (it != st[a[x]].begin())
        L = *(--it), q[++tot] = node(1, x, res[x] = x - L, id, L);
      if (L && R) q[++tot] = node(1, R, L - R, id, L);
      st[a[x]].insert(x);
    } else {
      q[++tot] = node(2, x, y, ++id, 0);
    }
  }
  solve(1, tot);
  for (int i = 1; i <= id; i++) printf("%lld\n", ans[i]);
  return 0;
}
