#include <bits/stdc++.h>
using namespace std;
struct rec {
  int x, y, t, k, w, be;
  rec() {}
  rec(int x, int y, int t, int k, int w, int be)
      : x(x), y(y), t(t), k(k), w(w), be(be) {}
} a[100010 * 8], tmp[100010 * 8];
set<int> se[100010];
int b[100010];
long long c[100010], ans[100010];
int n, m, cnt;
void add(int x, int w) {
  for (; x <= n; x += x & -x) c[x] += w;
}
long long getsum(int x) {
  int ans = 0;
  for (; x; x -= x & -x) ans += c[x];
  return ans;
}
bool cmp(const rec &a, const rec &b) {
  return a.y < b.y || a.y == b.y && a.k < b.k;
}
void solve(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  for (int i = l; i <= r; ++i)
    if (a[i].t <= mid && a[i].k == 1)
      add(a[i].x, a[i].w);
    else if (a[i].t > mid && a[i].k == 2)
      ans[a[i].be] += getsum(a[i].x) * a[i].w;
  for (int i = l; i <= r; ++i)
    if (a[i].t <= mid && a[i].k == 1) add(a[i].x, -a[i].w);
  int long long = l, rr = mid + 1;
  for (int i = l; i <= r; ++i)
    if (a[i].t <= mid)
      tmp[long long ++] = a[i];
    else
      tmp[rr++] = a[i];
  for (int i = l; i <= r; ++i) a[i] = tmp[i];
  solve(l, mid);
  solve(mid + 1, r);
}
int main() {
  scanf("%d%d", &n, &m);
  int x, y, z, k, tot = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x);
    b[i] = x;
    if (!se[x].empty()) {
      auto it = se[x].end();
      --it;
      ++tot;
      a[tot] = rec(i, *it, tot, 1, i - (*it), 0);
    }
    se[x].insert(i);
  }
  while (m--) {
    scanf("%d%d%d", &k, &x, &y);
    if (k == 1) {
      z = b[x];
      b[x] = y;
      auto it = se[z].find(x);
      if (it != se[z].begin()) {
        auto it1 = it;
        --it1;
        int l = x - (*it1);
        ++tot;
        a[tot] = rec(x, *it1, tot, 1, -l, 0);
        auto it2 = it;
        ++it2;
        if (it2 != se[z].end()) {
          int l = (*it2) - x;
          ++tot;
          a[tot] = rec(*it2, x, tot, 1, -l, 0);
          l = (*it2) - (*it1);
          ++tot;
          a[tot] = rec(*it2, *it1, tot, 1, l, 0);
        }
      } else {
        auto it2 = it;
        ++it2;
        int l = (*it2) - x;
        if (it2 != se[z].end()) {
          ++tot;
          a[tot] = rec(*it2, x, tot, 1, -l, 0);
        }
      }
      se[z].erase(it);
      if (!se[y].empty()) {
        auto it = se[y].lower_bound(x);
        if (it == se[y].begin()) {
          int l = (*it) - x;
          ++tot;
          a[tot] = rec(*it, x, tot, 1, l, 0);
        } else if (it == se[y].end()) {
          --it;
          int l = x - (*it);
          ++tot;
          a[tot] = rec(x, *it, tot, 1, l, 0);
        } else {
          auto it1 = it;
          --it1;
          int l = x - (*it1);
          ++tot;
          a[tot] = rec(x, *it1, tot, 1, l, 0);
          l = (*it) - x;
          ++tot;
          a[tot] = rec(*it, x, tot, 1, l, 0);
          l = (*it) - (*it1);
          ++tot;
          a[tot] = rec(*it, *it1, tot, 1, -l, 0);
        }
      }
      se[y].insert(x);
    } else {
      ++cnt;
      ++tot;
      a[tot] = rec(y, y, tot, 2, 1, cnt);
      ++tot;
      a[tot] = rec(y, x - 1, tot, 2, -1, cnt);
      ++tot;
      a[tot] = rec(x - 1, y, tot, 2, -1, cnt);
      ++tot;
      a[tot] = rec(x - 1, x - 1, tot, 2, 1, cnt);
    }
  }
  sort(a + 1, a + tot + 1, cmp);
  solve(1, tot);
  for (int i = 1; i <= cnt; ++i) printf("%lld\n", ans[i]);
  return 0;
}
