#include <bits/stdc++.h>
using namespace std;
const long long N = 100001;
long long a[N], ans[N];
set<long long> pos[N];
long long nx[N];
long long timer = 0;
struct Mem1 {
  long long i, x, v;
};
vector<long long> c[N];
vector<Mem1> mem1[N];
void upd_(long long i) {
  long long v = nx[i] - i;
  for (long long k = i; k < N; k |= k + 1) {
    c[k].push_back(nx[i]);
    mem1[timer].push_back({k, nx[i], v});
  }
}
void upd(long long i, long long to) {
  long long v = nx[i] - i;
  for (long long k = i; k < N; k |= k + 1) {
    mem1[timer].push_back({k, nx[i], -v});
  }
  nx[i] = to;
  v = nx[i] - i;
  for (long long k = i; k < N; k |= k + 1) {
    c[k].push_back(nx[i]);
    mem1[timer].push_back({k, nx[i], v});
  }
}
struct Mem {
  long long i, q, f, x;
};
vector<Mem> mem[N];
void get(long long q, long long f, long long i, long long x) {
  for (; i >= 0; i &= i + 1, --i) {
    mem[timer].push_back({i, q, f, x});
  }
}
bool quer[N];
vector<long long> f[N];
void add(long long i, long long x, long long v) {
  long long p = lower_bound(c[i].begin(), c[i].end(), x) - c[i].begin();
  for (; p < c[i].size(); p |= p + 1) {
    f[i][p] += v;
  }
}
long long get(long long i, long long x) {
  long long p = upper_bound(c[i].begin(), c[i].end(), x) - c[i].begin() - 1;
  long long ans = 0;
  for (; p >= 0; p &= p + 1, --p) {
    ans += f[i][p];
  }
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; ++i) nx[i] = N;
  for (long long i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (long long i = 1; i <= n; ++i) {
    if (pos[a[i]].size()) {
      nx[*pos[a[i]].rbegin()] = i;
    }
    pos[a[i]].insert(i);
  }
  for (long long i = 1; i <= n; ++i) {
    upd_(i);
  }
  for (timer = 0; timer < m; ++timer) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long p, x;
      cin >> p >> x;
      if (a[p] != x) {
        auto t = pos[a[p]].find(p);
        if (t != pos[a[p]].begin()) {
          auto l = t;
          --l;
          auto r = t;
          ++r;
          if (r == pos[a[p]].end())
            upd(*l, N);
          else
            upd(*l, *r);
        }
        pos[a[p]].erase(t);
        a[p] = x;
        pos[x].insert(p);
        t = pos[x].find(p);
        auto r = t;
        ++r;
        if (r == pos[x].end())
          upd(p, N);
        else
          upd(p, *r);
        if (t != pos[x].begin()) {
          auto l = t;
          --l;
          upd(*l, *t);
        }
      }
    } else {
      quer[timer] = 1;
      long long l, r;
      cin >> l >> r;
      get(timer, 1, r, r);
      get(timer, -1, l - 1, r);
    }
  }
  for (long long i = 0; i < N; ++i) {
    sort(c[i].begin(), c[i].end());
    c[i].resize(unique(c[i].begin(), c[i].end()) - c[i].begin());
    f[i].resize(c[i].size());
  }
  for (long long i = 0; i < N; ++i) {
    for (auto e : mem1[i]) {
      add(e.i, e.x, e.v);
    }
    for (auto e : mem[i]) {
      ans[e.q] += get(e.i, e.x) * e.f;
    }
  }
  for (long long i = 0; i < m; ++i) {
    if (quer[i]) cout << ans[i] << '\n';
  }
}
