#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)1e5 + 22;
vector<vector<int> > cr;
int N, M;
vector<vector<int> > qq;
int A[MAXN], prv[MAXN], nxt[MAXN], lst[MAXN];
struct Fenwick {
  int n;
  vector<long long> t, w;
  void init(int _n) {
    n = _n;
    t.resize(n, 0);
    w.resize(n, 0);
  }
  long long sum(int r) {
    long long ans = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) ans += t[r];
    return ans;
  }
  void inc(int i, long long d) {
    w[i] += d;
    for (; i < n; i = (i | (i + 1))) t[i] += d;
  }
  long long sum(int l, int r) {
    if (l > r) return 0;
    return sum(r) - sum(l - 1);
  }
};
void updateCR(int v, int l, int r, int x) {
  cr[v].push_back(prv[x]);
  if (r - l == 1) return;
  int mid = (l + r) / 2;
  if (x < mid)
    updateCR(2 * v + 1, l, mid, x);
  else
    updateCR(2 * v + 2, mid, r, x);
}
vector<Fenwick> T;
void build(int v, int l, int r) {
  cr[v].push_back(-1);
  sort(cr[v].begin(), cr[v].end());
  cr[v].resize(unique(cr[v].begin(), cr[v].end()) - cr[v].begin());
  T[v].init((int)cr[v].size());
  for (int i = l; i < r; i++) {
    int pos = lower_bound(cr[v].begin(), cr[v].end(), prv[i]) - cr[v].begin();
    assert(cr[v][pos] == prv[i]);
    T[v].inc(pos, i - prv[i]);
  }
  if (r - l == 1) return;
  int mid = (l + r) / 2;
  build(2 * v + 1, l, mid);
  build(2 * v + 2, mid, r);
}
long long get(int v, int l, int r, int ql, int qr) {
  if (ql >= r || qr <= l) return 0;
  if (ql <= l && r <= qr) {
    int pos = lower_bound(cr[v].begin(), cr[v].end(), ql) - cr[v].begin();
    int sz = (int)cr[v].size();
    return T[v].sum(pos, sz - 1);
  }
  int mid = (l + r) / 2;
  long long a, b;
  a = get(2 * v + 1, l, mid, ql, qr);
  b = get(2 * v + 2, mid, r, ql, qr);
  return a + b;
}
void update(int v, int l, int r, int x, int d) {
  int pos = lower_bound(cr[v].begin(), cr[v].end(), prv[x]) - cr[v].begin();
  assert(pos < (int)cr[v].size());
  if (cr[v][pos] != prv[x]) cerr << cr[v][pos] << " " << prv[x] << endl;
  assert(cr[v][pos] == prv[x]);
  T[v].inc(pos, d * (x - prv[x]));
  if (r - l == 1) return;
  int mid = (l + r) / 2;
  if (x < mid)
    update(2 * v + 1, l, mid, x, d);
  else
    update(2 * v + 2, mid, r, x, d);
}
void input() {
  cin >> N >> M;
  memset(lst, -1, sizeof(lst));
  memset(nxt, -1, sizeof(nxt));
  cr.resize(4 * N);
  vector<set<int> > st;
  st.resize(N + 1);
  vector<int> B;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    B.push_back(A[i]);
    st[A[i]].insert(i);
    prv[i] = lst[A[i]];
    if (prv[i] >= 0) nxt[prv[i]] = i;
    updateCR(0, 0, N, i);
    lst[A[i]] = i;
  }
  int type, a, b;
  for (int i = 0; i < M; i++) {
    cin >> type >> a >> b;
    --type, --a;
    qq.push_back({type, a, b});
    if (!type) {
      if (prv[a] >= 0) nxt[prv[a]] = nxt[a];
      if (nxt[a] >= 0) {
        prv[nxt[a]] = prv[a];
        updateCR(0, 0, N, nxt[a]);
      }
      st[B[a]].erase(a);
      B[a] = b;
      st[B[a]].insert(a);
      auto it = st[B[a]].lower_bound(a);
      if (it != st[B[a]].begin()) {
        --it;
        nxt[*it] = a;
        prv[a] = *it;
        ++it;
      } else
        prv[a] = -1;
      updateCR(0, 0, N, a);
      ++it;
      if (it != st[B[a]].end()) {
        prv[*it] = a;
        nxt[a] = *it;
        updateCR(0, 0, N, nxt[a]);
      } else
        nxt[a] = -1;
    }
  }
}
void solve() {
  memset(lst, -1, sizeof(lst));
  memset(nxt, -1, sizeof(nxt));
  vector<set<int> > st;
  st.resize(N + 1);
  vector<int> B;
  for (int i = 0; i < N; i++) {
    B.push_back(A[i]);
    st[A[i]].insert(i);
    prv[i] = lst[A[i]];
    if (prv[i] >= 0) nxt[prv[i]] = i;
    lst[A[i]] = i;
  }
  T.resize(4 * N);
  build(0, 0, N);
  int type, a, b;
  for (int i = 0; i < M; i++) {
    type = qq[i][0];
    a = qq[i][1];
    b = qq[i][2];
    if (type)
      cout << get(0, 0, N, a, b) << "\n";
    else {
      update(0, 0, N, a, -1);
      if (prv[a] >= 0) {
        nxt[prv[a]] = nxt[a];
      }
      if (nxt[a] >= 0) {
        update(0, 0, N, nxt[a], -1);
        prv[nxt[a]] = prv[a];
        update(0, 0, N, nxt[a], 1);
      }
      st[B[a]].erase(a);
      B[a] = b;
      st[B[a]].insert(a);
      auto it = st[B[a]].lower_bound(a);
      ++it;
      if (it != st[B[a]].end()) {
        nxt[a] = *it;
        update(0, 0, N, nxt[a], -1);
        prv[*it] = a;
        update(0, 0, N, nxt[a], 1);
      } else
        nxt[a] = -1;
      --it;
      if (it != st[B[a]].begin()) {
        --it;
        nxt[*it] = a;
        prv[a] = *it;
        ++it;
      } else
        prv[a] = -1;
      update(0, 0, N, a, 1);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  input();
  solve();
  return 0;
}
