#include <bits/stdc++.h>
using namespace std;
const int BLOCK = 50;
const int BLOCKSZ = 2048;
const int MAXN = 1e5 + 5;
int N, M;
set<int> spots[MAXN];
int arr[MAXN];
int stored[BLOCK][BLOCK];
int lbnd[MAXN];
int rbnd[MAXN];
int first_of[BLOCK][MAXN];
int last_of[BLOCK][MAXN];
int prev_pos[MAXN];
int nxt_pos[MAXN];
int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);
  cin >> N >> M;
  for (int a = 0; a < N; a++) {
    nxt_pos[a] = -1;
    prev_pos[a] = 200000;
    cin >> arr[a];
    if (!spots[arr[a]].empty()) {
      prev_pos[a] = *prev(spots[arr[a]].end());
      nxt_pos[*prev(spots[arr[a]].end())] = a;
    }
    spots[arr[a]].insert(a);
  }
  for (int a = 0; a * BLOCKSZ < N; a++) {
    int sum = 0;
    fill(lbnd, lbnd + MAXN, -1);
    fill(rbnd, rbnd + MAXN, -1);
    for (int b = a * BLOCKSZ; b < N; b++) {
      if (b % BLOCKSZ == BLOCKSZ - 1) {
        stored[a][b / BLOCKSZ] = sum;
      }
      if (lbnd[arr[b]] == -1) {
        lbnd[arr[b]] = rbnd[arr[b]] = b;
      } else {
        sum += b - rbnd[arr[b]];
        rbnd[arr[b]] = b;
      }
    }
  }
  for (int a = 0; a < BLOCK; a++) {
    fill(first_of[a], first_of[a] + MAXN, 200000);
    fill(last_of[a], last_of[a] + MAXN, -1);
  }
  for (int a = 0; a < N; a++) {
    first_of[a / BLOCKSZ][arr[a]] = min(first_of[a / BLOCKSZ][arr[a]], a);
    last_of[a / BLOCKSZ][arr[a]] = max(last_of[a / BLOCKSZ][arr[a]], a);
  }
  while (M--) {
    int tp;
    cin >> tp;
    if (tp == 1) {
      int p, x;
      cin >> p >> x;
      p--;
      if (arr[p] == x) {
        continue;
      }
      for (int a = 0; a * BLOCKSZ < N; a++) {
        int lx = 200000, rx = -1;
        int lp = 200000, rp = -1;
        for (int b = a; (b + 1) * BLOCKSZ - 1 < N; b++) {
          lx = min(lx, first_of[b][x]);
          rx = max(rx, last_of[b][x]);
          lp = min(lp, first_of[b][arr[p]]);
          rp = max(rp, last_of[b][arr[p]]);
          stored[a][b] -= max(0, rx - lx);
          stored[a][b] -= max(0, rp - lp);
        }
      }
      if (nxt_pos[p] != -1) {
        prev_pos[nxt_pos[p]] = prev_pos[p];
      }
      if (prev_pos[p] != 200000) {
        nxt_pos[prev_pos[p]] = nxt_pos[p];
      }
      nxt_pos[p] = -1;
      prev_pos[p] = 200000;
      spots[arr[p]].erase(p);
      auto iter = spots[x].lower_bound(p);
      if (iter != spots[x].end()) {
        nxt_pos[p] = *iter;
        prev_pos[*iter] = p;
      }
      if (iter != spots[x].begin()) {
        nxt_pos[*prev(iter)] = p;
        prev_pos[p] = *prev(iter);
      }
      int block_id = p / BLOCKSZ;
      for (int a = block_id * BLOCKSZ; a < N && a < (block_id + 1) * BLOCKSZ;
           a++) {
        first_of[block_id][arr[a]] = 200000;
        last_of[block_id][arr[a]] = -1;
      }
      int prev_val = arr[p];
      arr[p] = x;
      spots[arr[p]].insert(p);
      for (int a = block_id * BLOCKSZ; a < N && a < (block_id + 1) * BLOCKSZ;
           a++) {
        first_of[a / BLOCKSZ][arr[a]] = min(first_of[a / BLOCKSZ][arr[a]], a);
        last_of[a / BLOCKSZ][arr[a]] = max(last_of[a / BLOCKSZ][arr[a]], a);
      }
      for (int a = 0; a * BLOCKSZ < N; a++) {
        int lx = 200000, rx = -1;
        int lp = 200000, rp = -1;
        for (int b = a; (b + 1) * BLOCKSZ - 1 < N; b++) {
          lx = min(lx, first_of[b][x]);
          rx = max(rx, last_of[b][x]);
          lp = min(lp, first_of[b][arr[p]]);
          rp = max(rp, last_of[b][arr[p]]);
          stored[a][b] += max(0, rx - lx);
          stored[a][b] += max(0, rp - lp);
        }
      }
    } else {
      int l, r;
      cin >> l >> r;
      l--, r--;
      if (r - l <= BLOCKSZ) {
        long long ans = 0;
        for (int a = l; a <= r; a++) {
          if (prev_pos[a] != 200000 && prev_pos[a] >= l) {
            ans += a - prev_pos[a];
          }
        }
        cout << ans << "\n";
        continue;
      }
      int lblock = (l + BLOCKSZ - 1) / BLOCKSZ;
      int rblock = r / BLOCKSZ;
      long long ans = stored[lblock][rblock];
      for (int a = lblock * BLOCKSZ - 1; a >= l; a--) {
        if (nxt_pos[a] != -1 && nxt_pos[a] <= r) {
          ans += nxt_pos[a] - a;
        }
      }
      for (int a = rblock * BLOCKSZ; a <= r; a++) {
        if (prev_pos[a] != 200000 && prev_pos[a] >= lblock * BLOCKSZ) {
          ans += a - prev_pos[a];
        }
      }
      cout << ans << "\n";
    }
  }
}
