#include <bits/stdc++.h>
using namespace std;
int Block[100010];
int freq[100010];
int a[100010], last[100010], Prev[100010], Next[100010], First[100010],
    Last[100010];
long long result[100010];
int Prev_a[100010];
set<int> Pos[100010];
struct Query {
  int l, r, id, Time;
} Q[100010];
inline bool compare(const Query &q1, const Query &q2) {
  return make_pair(make_pair(Block[q1.l], Block[q1.r]), q1.id) <
         make_pair(make_pair(Block[q2.l], Block[q2.r]), q2.id);
}
struct Update {
  int x, val, before;
} U[100010];
int p1, p2;
long long ans;
inline void add(int x, int val) {
  if (First[val] < 1) {
    First[val] = Last[val] = x;
    return;
  }
  if (x < First[val]) {
    ans += (First[val] - x);
    First[val] = x;
    return;
  }
  if (x > Last[val]) {
    ans += (x - Last[val]);
    Last[val] = x;
    return;
  }
}
inline void del(int x, int val) {
  if (x != First[val] && x != Last[val]) return;
  if (x == First[val] && x == Last[val]) {
    First[val] = Last[val] = -1;
    return;
  }
  if (x == Last[val]) {
    ans -= (x - Prev[x]);
    Last[val] = Prev[x];
    return;
  }
  ans -= (Next[x] - x);
  First[val] = Next[x];
}
inline void change(int x, int New) {
  if (a[x] == New) return;
  if (x >= p1 && x <= p2) {
    del(x, a[x]);
    add(x, New);
  }
  Next[Prev[x]] = Next[x];
  Prev[Next[x]] = Prev[x];
  if (Pos[New].size() == 0) {
    Prev[x] = 0;
    Next[x] = 100010 - 1;
  } else {
    auto it = Pos[New].upper_bound(x);
    int Before = 0, After = 100010 - 1;
    if (it != Pos[New].end()) After = *it;
    if (it != Pos[New].begin()) {
      --it;
      Before = *it;
    }
    Prev[x] = Before;
    Next[x] = After;
    Next[Before] = x;
    Prev[After] = x;
  }
  Pos[New].insert(x);
  Pos[a[x]].erase(x);
  a[x] = New;
}
int main() {
  int t = 1, i;
  for (i = 0; i < 100010; i++) Block[i] = i / 15000;
  while (t--) {
    int n, q;
    scanf("%d", &n);
    scanf("%d", &q);
    for (i = 0; i < 100010; i++) Pos[i].clear();
    for (i = 0; i < 100010; i++) First[i] = Last[i] = -1;
    for (i = 0; i < 100010; i++) Prev_a[i] = 0;
    for (i = 0; i < 100010; i++) Prev[i] = 0;
    for (i = 0; i < 100010; i++) Next[i] = 100010 - 1;
    int cnt_q = 0, cnt_u = 0;
    for (i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      Pos[a[i]].insert(i);
      Next[Prev_a[a[i]]] = i;
      Prev[i] = Prev_a[a[i]];
      Next[i] = 100010 - 1;
      Prev_a[a[i]] = i;
      last[i] = a[i];
    }
    for (i = 0; i < q; i++) {
      int type, x, y;
      scanf("%d", &type);
      scanf("%d", &x);
      scanf("%d", &y);
      if (type == 2) {
        ++cnt_q;
        Q[cnt_q] = (Query){x, y, cnt_q, cnt_u};
      } else {
        ++cnt_u;
        U[cnt_u] = (Update){x, y, last[x]};
        last[x] = y;
      }
    }
    sort(Q + 1, Q + cnt_q + 1, compare);
    p1 = 1, p2 = 0;
    int cur_update = 0;
    ans = 0;
    for (i = 1; i <= cnt_q; i++) {
      while (cur_update < Q[i].Time) {
        ++cur_update;
        change(U[cur_update].x, U[cur_update].val);
      }
      while (cur_update > Q[i].Time) {
        change(U[cur_update].x, U[cur_update].before);
        --cur_update;
      }
      while (p2 < Q[i].r) {
        ++p2;
        add(p2, a[p2]);
      }
      while (p1 > Q[i].l) {
        --p1;
        add(p1, a[p1]);
      }
      while (p2 > Q[i].r) {
        del(p2, a[p2]);
        p2--;
      }
      while (p1 < Q[i].l) {
        del(p1, a[p1]);
        p1++;
      }
      result[Q[i].id] = ans;
    }
    for (i = 1; i <= cnt_q; i++) printf("%lld\n", result[i]);
  }
}
