#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
const long long BIG = 1446803456761533460LL;
const int Big = 336860180;
const long long int INF = LONG_LONG_MAX;
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
long long int powMod(long long int a, long long int b) {
  long long int n = 1;
  while (b > 0) {
    if (b % 2 == 1) {
      n = (n * (a)) % MOD;
    }
    a = (a * (a)) % MOD;
    b /= 2;
  }
  return n;
}
long long int modularInverse(long long int a) { return powMod(a, MOD - 2); }
stringstream sss;
const long long int maxn = 100010;
const long long int SQ = 350;
const long long int maxnsq = maxn / SQ + 10;
long long int n, Q;
long long int ar[maxn];
set<long long int> idxs[maxn];
struct BIT {
  long long int fen[maxn];
  void update(long long int i, long long int v) {
    for (++i; i < maxn; i += i & (-i)) fen[i] += v;
  }
  long long int get(long long int i) {
    long long int s = 0;
    for (++i; i > 0; i -= i & (-i)) s += fen[i];
    return s;
  }
} mem[maxnsq];
void MAIN() {
  cin >> n >> Q;
  for (long long int i = (0); i < (n); ++i) {
    cin >> ar[i];
    idxs[ar[i]].insert(i);
  }
  for (long long int i = (0); i < (n); ++i) {
    auto nxt = idxs[ar[i]].upper_bound(i);
    if (nxt != idxs[ar[i]].end()) {
      mem[i / SQ].update(*nxt, *nxt - i);
    }
  }
  for (long long int q = (0); q < (Q); ++q) {
    long long int t, l, r;
    cin >> t >> l >> r;
    --l;
    if (t == 1) {
      auto prv = idxs[ar[l]].lower_bound(l);
      auto nxt = idxs[ar[l]].upper_bound(l);
      if (prv != idxs[ar[l]].begin()) {
        long long int lt = *(--prv);
        mem[lt / SQ].update(l, -(l - lt));
        if (nxt != idxs[ar[l]].end()) {
          mem[lt / SQ].update(*nxt, *nxt - lt);
        }
      }
      if (nxt != idxs[ar[l]].end()) {
        mem[l / SQ].update(*nxt, -(*nxt - l));
      }
      idxs[ar[l]].erase(l);
      ar[l] = r;
      idxs[ar[l]].insert(l);
      prv = idxs[ar[l]].lower_bound(l);
      nxt = idxs[ar[l]].upper_bound(l);
      if (prv != idxs[ar[l]].begin()) {
        long long int lt = *(--prv);
        mem[lt / SQ].update(l, l - lt);
        if (nxt != idxs[ar[l]].end()) {
          mem[lt / SQ].update(*nxt, -(*nxt - lt));
        }
      }
      if (nxt != idxs[ar[l]].end()) {
        mem[l / SQ].update(*nxt, *nxt - l);
      }
    } else {
      long long int ans = 0;
      while (l < r) {
        if (l % SQ == 0 && l + SQ < r) {
          ans += mem[l / SQ].get(r - 1);
          l += SQ;
        } else {
          auto nxt = idxs[ar[l]].upper_bound(l);
          if (nxt != idxs[ar[l]].end() && *nxt < r) {
            ans += *nxt - l;
          }
          ++l;
        }
      }
      cout << (ans) << '\n';
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
7 6
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6
2 5 7
    )";
  MAIN();
  return 0;
}
