#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, m, sqr, a[N], trb[N];
set<int> pos[N];
vector<int> t, l, r, ind;
vector<pair<int, int>> qry[N];
int64_t ans[N];
int64_t aib[N], prv[N], last[N];
void upAib(int x, int val) {
  for (++x; x <= n; x += x & -x) {
    aib[x] += val;
  }
}
int64_t aibQry(int poss) {
  int64_t sum = 0;
  for (++poss; poss > 0; poss -= poss & -poss) sum += aib[poss];
  return sum;
}
int64_t aibQry(int ax, int bx) { return aibQry(bx) - aibQry(ax - 1); }
void initPrv() {
  for (int x = 1; x <= n; ++x) last[x] = -1;
  for (int i = 0; i < n; ++i) {
    if (last[a[i]] != -1) {
      prv[i] = last[a[i]];
    } else
      prv[i] = -1;
    last[a[i]] = i;
  }
}
int costFor(int val, int x, int y) {
  auto it1 = pos[val].lower_bound(x);
  auto it2 = pos[val].upper_bound(y);
  it2--;
  if (it1 != end(pos[val])) {
    return *it2 - *it1;
  }
  return 0;
}
void update(int where, int val, int x, int y, int64_t &s) {
  s -= costFor(a[where], x, y);
  pos[a[where]].erase(where);
  s += costFor(a[where], x, y);
  s -= costFor(val, x, y);
  a[where] = val;
  pos[a[where]].insert(where);
  s += costFor(a[where], x, y);
}
vector<vector<int>> undo;
void StergeSet(set<int> &that, int x) {
  auto it = that.lower_bound(x);
  if (it != end(that) && *it == x) that.erase(it);
}
void solve() {
  for (int i = 0; i < n; ++i) qry[i].clear();
  for (int i = 0; i < t.size(); ++i) {
    if (t[i] == 2) {
      qry[r[i]].emplace_back(l[i], ind[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    aib[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    if (prv[i] != -1) {
      upAib(prv[i], i - prv[i]);
    }
    for (auto it : qry[i]) {
      ans[it.second] = aibQry(it.first, i);
    }
  }
  for (int i = 0; i < t.size(); ++i) {
    if (t[i] == 2) {
      int X = l[i], Y = r[i];
      undo.clear();
      for (int j = 0; j < i; ++j) {
        if (t[j] == 2) continue;
        undo.push_back({l[j], a[l[j]], r[j]});
      }
      for (int j = 0; j < i; ++j) {
        if (t[j] == 2) continue;
        update(l[j], r[j], X, Y, ans[ind[i]]);
      }
      for (auto it : undo) {
        StergeSet(pos[it[2]], it[0]);
        pos[it[0]].insert(it[1]);
      }
    }
  }
  for (int i = 0; i < t.size(); ++i) {
    if (t[i] == 1) {
      pos[a[l[i]]].erase(l[i]);
      pos[r[i]].insert(l[i]);
      a[l[i]] = r[i];
    }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  sqr = sqrt(m) + 1;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    pos[a[i]].insert(i);
  }
  initPrv();
  for (int i = 0; i < m; ++i) {
    int aux1, aux2, aux3;
    scanf("%d %d %d", &aux1, &aux2, &aux3);
    if (aux1 == 2) {
      --aux2;
      --aux3;
      trb[i] = 1;
    } else {
      --aux2;
    }
    t.push_back(aux1);
    l.push_back(aux2);
    r.push_back(aux3);
    ind.push_back(i);
    if (t.size() == sqr || i == m - 1) {
      solve();
      t.clear();
      l.clear();
      r.clear();
      ind.clear();
      initPrv();
    }
  }
  for (int i = 0; i < m; ++i)
    if (trb[i]) printf("%I64d\n", ans[i]);
}
