#include <bits/stdc++.h>
using namespace std;
const int N = int(1e5) + 5;
const int inf = (int)1e8 + 7;
const int B = 300;
struct bit {
  map<int, long long> t;
  void inc(int v, int val) {
    for (; v < N; v += v & -v) {
      t[v] += val;
    }
  }
  long long get(int v) {
    long long ans = 0;
    for (; v > 0; v -= v & -v) {
      if (t.count(v)) {
        ans += t[v];
      }
    }
    return ans;
  }
};
int id[N];
bit e[405];
int n, q;
int a[N], nxt[N];
void upd(int pos, pair<int, int> val, pair<int, int> old) {
  --pos;
  if (old.first) {
    e[id[pos]].inc(old.first, -old.first);
  }
  e[id[pos]].inc(val.first, val.second);
}
long long get(int l, int r) {
  --l, --r;
  long long ans = 0;
  if (id[l] == id[r]) {
    for (int j = l; j <= r; ++j) {
      if (nxt[j + 1] <= r + 1) {
        ans += nxt[j + 1] - (j + 1);
      }
    }
  } else {
    for (int j = l; j < (id[l] + 1) * B; ++j) {
      if (nxt[j + 1] <= r + 1) {
        ans += (nxt[j + 1] - 1) - j;
      }
    }
    for (int j = r; j >= id[r] * B; --j) {
      if (nxt[j + 1] <= r + 1) {
        ans += (nxt[j + 1] - 1) - j;
      }
    }
    for (int j = id[l] + 1; j < id[r]; ++j) {
      ans += e[j].get(r + 1);
    }
  }
  return ans;
}
set<int> pos[N];
void recalc(int np) {
  if (np == -1) {
    return;
  }
  auto it = pos[a[np]].upper_bound(np);
  int nw = it == pos[a[np]].end() ? n + 1 : *it;
  upd(np, make_pair(nw, nw - np), make_pair(nxt[np], nxt[np] - np));
  nxt[np] = nw;
}
int get_previous(int np) {
  auto it = pos[a[np]].lower_bound(np);
  if (it == pos[a[np]].begin()) {
    return -1;
  } else {
    --it;
    return *it;
  }
}
int get_next(int np) {
  auto it = pos[a[np]].upper_bound(np);
  if (it == pos[a[np]].end()) {
    return -1;
  } else {
    return *it;
  }
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; ++i) {
    id[i] = i / B;
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    pos[a[i]].insert(i);
  }
  for (int i = 1; i <= n; ++i) {
    recalc(i);
  }
  for (int i = 1; i <= q; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int p, x;
      scanf("%d %d", &p, &x);
      if (a[p] == x) {
        continue;
      }
      int w = get_previous(p);
      pos[a[p]].erase(p);
      a[p] = x;
      recalc(w);
      pos[x].insert(p);
      recalc(p);
      w = get_previous(p);
      recalc(w);
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      printf("%lld\n", get(l, r));
    }
  }
  return 0;
}
