#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int C = 26;
void add(int &x, int y) {
  x += y;
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
}
int fix(int x) {
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
  return x;
}
int pw(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    b >>= 1;
    a = 1ll * a * a % MOD;
  }
  return ret;
}
const int MAXN = 1e5 + 10;
const int SQ = 300;
struct BIT {
  long long ft[MAXN] = {};
  void upd(int i, long long x) {
    for (++i; i < MAXN; i += i & -i) {
      ft[i] += x;
    }
  }
  long long get(int i) {
    long long s = 0;
    for (++i; i; i -= i & -i) {
      s += ft[i];
    }
    return s;
  }
  long long sum_range(int i, int j) { return get(j) - get(i - 1); }
  void clear() { memset(ft, 0, sizeof(ft)); }
} DS[SQ + 1];
int block(int i) {
  int r = i / (MAXN / SQ);
  return r;
}
set<int> s[MAXN];
int a[MAXN], b[MAXN];
bool vec[MAXN];
long long ans[MAXN];
array<int, 3> qry[MAXN];
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    --a[i];
    s[a[i]].insert(i);
  }
  memcpy(b, a, sizeof(a));
  for (int i = 0; i < n; i++) {
    s[i].insert(0);
    s[i].insert(n + 1);
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> qry[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    auto it = s[a[i]].upper_bound(i);
    DS[block(i)].upd(*it, i);
  }
  for (int i = 0; i < m; i++) {
    int ty = qry[i][0];
    if (ty == 1) {
      int p = qry[i][1], x = qry[i][2];
      --x;
      auto it = s[a[p]].upper_bound(p), it2 = it;
      DS[block(p)].upd(*it, -p);
      --it;
      --it;
      if (it != s[a[p]].begin()) {
        DS[block(*it)].upd(p, -(*it));
        DS[block(*it)].upd(*it2, *it);
      }
      s[a[p]].erase(p);
      a[p] = x;
      s[a[p]].insert(p);
      it = s[a[p]].upper_bound(p), it2 = it;
      DS[block(p)].upd(*it, p);
      --it;
      --it;
      if (it != s[a[p]].begin()) {
        DS[block(*it)].upd(*it2, -(*it));
        DS[block(*it)].upd(p, *it);
      }
    } else {
      int l = qry[i][1], r = qry[i][2];
      int L = block(l) + 1, R = block(r) - 1;
      long long ret = 0;
      for (int j = L; j <= R; j++) {
        ret += DS[j].sum_range(r + 1, MAXN - 2);
      }
      for (int j = l; j <= r && block(j) == block(l); j++) {
        int x = a[j];
        auto it = s[x].upper_bound(j);
        if (*it > r) {
          ret += j;
        }
      }
      if (block(l) ^ block(r)) {
        int me = block(r);
        for (int j = r; block(j) == me; --j) {
          int x = a[j];
          if (!vec[x]) {
            ret += j;
          }
          vec[x] = 1;
        }
        for (int j = r; block(j) == me; --j) {
          int x = a[j];
          vec[x] = 0;
        }
      }
      ans[i] += ret;
    }
  }
  for (int i = 0; i <= SQ; i++) {
    DS[i].clear();
  }
  for (int i = 0; i < n; i++) {
    s[i].clear();
  }
  memcpy(a, b, sizeof(b));
  for (int i = 1; i <= n; i++) {
    s[a[i]].insert(i);
  }
  for (int i = 0; i < n; i++) {
    s[i].insert(0);
    s[i].insert(n + 1);
  }
  for (int i = 1; i <= n; i++) {
    auto it = s[a[i]].lower_bound(i);
    --it;
    DS[block(i)].upd(*it, i);
  }
  for (int i = 0; i < m; i++) {
    int ty = qry[i][0];
    if (ty == 1) {
      int p = qry[i][1], x = qry[i][2];
      --x;
      ;
      auto it = s[a[p]].lower_bound(p);
      --it;
      auto it2 = it;
      DS[block(p)].upd(*it, -p);
      ++it;
      ++it;
      if (it != --s[a[p]].end()) {
        DS[block(*it)].upd(p, -(*it));
        DS[block(*it)].upd(*it2, *it);
      }
      s[a[p]].erase(p);
      a[p] = x;
      it = s[a[p]].lower_bound(p);
      --it;
      it2 = it;
      DS[block(p)].upd(*it, p);
      s[a[p]].insert(p);
      ++it;
      ++it;
      if (it != --s[a[p]].end()) {
        DS[block(*it)].upd(*it2, -(*it));
        DS[block(*it)].upd(p, *it);
      }
    } else {
      int l = qry[i][1], r = qry[i][2];
      int L = block(l) + 1, R = block(r) - 1;
      long long ret = 0;
      for (int j = L; j <= R; j++) {
        ret += DS[j].sum_range(0, l - 1);
      }
      for (int j = l; j <= r && block(j) == block(l); j++) {
        int x = a[j];
        if (!vec[x]) {
          ret += j;
        }
        vec[x] = 1;
      }
      for (int j = l; j <= r && block(j) == block(l); j++) {
        int x = a[j];
        vec[x] = 0;
      }
      if (block(l) ^ block(r)) {
        for (int j = r; block(j) == block(r); --j) {
          int x = a[j];
          auto it = s[x].lower_bound(j);
          --it;
          if (*it < l) {
            ret += j;
          }
        }
      }
      ans[i] -= ret;
    }
  }
  for (int i = 0; i < m; i++) {
    if (qry[i][0] == 2) {
      cout << ans[i] << "\n";
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int te = 1;
  for (int w = 1; w <= te; w++) {
    solve();
  }
  return 0;
}
