#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const long long linf = (long long)1e18;
const double eps = (double)1e-8;
const int mod = (int)1e9 + 7;
const int maxn = (int)1.1e5 + 5;
const int maxsqn = (int)400 + 5;
const int MX = (int)1e5;
int askdkaslvv[maxn], nxt[maxn];
int a[maxn];
set<int> pos[maxn];
int n, m, st_n, sq, sqn;
long long sqans[maxsqn][maxsqn];
void add(int p, int val, long long& ans, int l, int r, int mult = 1) {
  if (p < l || p > r) return;
  if (askdkaslvv[p] == 0 || askdkaslvv[p] < l) {
    ans -= mult * p;
    if (nxt[p] != 0 && nxt[p] <= r) ans += mult * nxt[p];
  }
  if (nxt[p] == 0 || nxt[p] > r) {
    ans += mult * p;
    if (askdkaslvv[p] != 0 && askdkaslvv[p] >= l) ans -= mult * askdkaslvv[p];
  }
}
void del(int p, int val, long long& ans, int l, int r) {
  add(p, val, ans, l, r, -1);
}
void change(int p, int val) {
  for (int i = (1); i <= (int)(sqn); ++i) {
    for (int j = (i); j <= (int)(sqn); ++j) {
      int st = sq * (i - 1) + 1, en = sq * j;
      del(p, a[p], sqans[i][j], st, en);
    }
  }
  if (nxt[p] != 0) askdkaslvv[nxt[p]] = askdkaslvv[p];
  if (askdkaslvv[p] != 0) nxt[askdkaslvv[p]] = nxt[p];
  pos[a[p]].erase(p);
  a[p] = val;
  auto it = pos[a[p]].insert(p).first;
  set<int>::iterator itl, itr;
  itl = it, itr = it;
  if (it != pos[a[p]].begin())
    askdkaslvv[p] = *(--itl);
  else
    askdkaslvv[p] = 0;
  ++itr;
  if (itr != pos[a[p]].end())
    nxt[p] = *itr;
  else
    nxt[p] = 0;
  if (nxt[p] != 0) askdkaslvv[nxt[p]] = p;
  if (askdkaslvv[p] != 0) nxt[askdkaslvv[p]] = p;
  for (int i = (1); i <= (int)(sqn); ++i) {
    for (int j = (i); j <= (int)(sqn); ++j) {
      int st = sq * (i - 1) + 1, en = sq * j;
      add(p, a[p], sqans[i][j], st, en);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  st_n = n;
  sq = pow(n, 2. / 3);
  while (n % sq != 0) {
    ++n;
  }
  sqn = n / sq;
  memset((nxt), 0, sizeof(nxt));
  memset((askdkaslvv), 0, sizeof(askdkaslvv));
  for (int i = (1); i <= (int)(n); ++i) {
    a[i] = i;
    pos[a[i]].insert(i);
  }
  for (int i = (1); i <= (int)(st_n); ++i) {
    int x;
    cin >> x;
    change(i, x);
  }
  for (int(numt) = (1); (numt) <= (int)(m); ++(numt)) {
    int typ;
    cin >> typ;
    if (typ == 1) {
      int p, x;
      cin >> p >> x;
      change(p, x);
    } else {
      int l, r;
      int gl = 0, gr = 0;
      cin >> l >> r;
      if (r - l + 1 <= 2 * sq) {
        long long ans = 0;
        for (int i = (l); i <= (int)(r); ++i) {
          add(i, a[i], ans, l, i);
        }
        cout << ans << "\n";
        continue;
      }
      for (int i = (1); i <= (int)(sqn); ++i) {
        int st = sq * (i - 1) + 1, en = st + sq - 1;
        if (st >= l) {
          if (gl == 0) gl = i;
        }
        if (en <= r) gr = i;
      }
      long long ans = sqans[gl][gr];
      for (int i = (sq * gr + 1); i <= (int)(r); ++i)
        add(i, a[i], ans, sq * (gl - 1) + 1, i);
      for (int i = (sq * (gl - 1)); i >= (int)(l); --i) add(i, a[i], ans, i, r);
      cout << ans << "\n";
    }
  }
  return 0;
}
