#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Node {
  int k, x, y, v;
  Node(int k = 0, int x = 0, int y = 0, int v = 0) : k(k), x(x), y(y), v(v) {}
};
struct Event {
  int k, pos, l, r, v;
  Event(int k = 0, int pos = 0, int l = 0, int r = 0, int v = 0)
      : k(k), pos(pos), l(l), r(r), v(v) {}
  bool operator<(const Event &rhs) const {
    return pos < rhs.pos || (pos == rhs.pos && k < rhs.k);
  }
};
int n, q;
int base, tot, tol;
int pre[N], a[N];
long long ans[N];
long long seg_tree[1 << 20];
Node nodes[N << 3];
Event events[N << 3];
set<int> col[N];
void add(int x, int v) {
  for (x += base; x; x >>= 1) seg_tree[x] += v;
}
long long query(int l, int r) {
  long long ret = 0;
  l += base - 1;
  r += base + 1;
  for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (~l & 1) ret += seg_tree[l ^ 1];
    if (r & 1) ret += seg_tree[r ^ 1];
  }
  return ret;
}
inline void change(int pos, int val) {
  if (a[pos] == val) return;
  auto it = col[a[pos]].find(pos);
  int pre = -1;
  int aft = -1;
  if (it != col[a[pos]].begin()) {
    --it;
    pre = *it;
    ++it;
    nodes[++tot] = Node(0, pos, pre, -(pos - pre));
  }
  ++it;
  if (it != col[a[pos]].end()) {
    aft = *it;
    nodes[++tot] = Node(0, aft, pos, -(aft - pos));
  }
  if (pre != -1 && aft != -1) {
    nodes[++tot] = Node(0, aft, pre, aft - pre);
  }
  col[a[pos]].erase(pos);
  a[pos] = val;
  it = col[val].insert(pos).first;
  pre = -1;
  aft = -1;
  if (it != col[val].begin()) {
    --it;
    pre = *it;
    ++it;
    nodes[++tot] = Node(0, pos, pre, pos - pre);
  }
  ++it;
  if (it != col[val].end()) {
    aft = *it;
    nodes[++tot] = Node(0, aft, pos, aft - pos);
  }
  if (pre != -1 && aft != -1) {
    nodes[++tot] = Node(0, aft, pre, -(aft - pre));
  }
}
void solve(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  tol = 0;
  for (int i = l; i <= mid; ++i)
    if (nodes[i].k == 0) {
      events[tol++] = Event(0, nodes[i].x, nodes[i].y, 0, nodes[i].v);
    }
  for (int i = mid + 1; i <= r; ++i)
    if (nodes[i].k == 1) {
      events[tol++] =
          Event(1, nodes[i].x - 1, nodes[i].x, nodes[i].y, nodes[i].v);
      events[tol++] = Event(2, nodes[i].y, nodes[i].x, nodes[i].y, nodes[i].v);
    }
  sort(events, events + tol);
  for (int i = 0; i < tol; ++i) {
    if (events[i].k == 0) {
      add(events[i].l, events[i].v);
    } else if (events[i].k == 1) {
      ans[events[i].v] -= query(events[i].l, events[i].r);
    } else {
      ans[events[i].v] += query(events[i].l, events[i].r);
    }
  }
  for (int i = 0; i < tol; ++i)
    if (events[i].k == 0) {
      add(events[i].l, -events[i].v);
    }
}
int main() {
  while (~scanf("%d%d", &n, &q)) {
    for (base = 1; base <= n + 1; base <<= 1)
      ;
    for (int i = 0; i <= base << 1; ++i) seg_tree[i] = 0;
    tot = 0;
    int x, l, r;
    for (int i = 1; i <= n; ++i) {
      pre[i] = 1;
      col[i].clear();
    }
    for (int i = 2; i <= n + 1; ++i) {
      scanf("%d", &x);
      nodes[++tot] = Node(0, i, pre[x], i - pre[x]);
      pre[x] = i;
      col[x].insert(i);
      a[i] = x;
    }
    for (int i = 1; i <= q; ++i) {
      scanf("%d%d%d", &x, &l, &r);
      if (x == 1) {
        change(l + 1, r);
        ans[i] = -1;
      } else {
        ++l;
        ++r;
        nodes[++tot] = Node(1, l, r, i);
        ans[i] = 0;
      }
    }
    solve(1, tot);
    for (int i = 1; i <= q; ++i)
      if (ans[i] != -1) printf("%I64d\n", ans[i]);
  }
}
