#include <bits/stdc++.h>
using namespace std;
template <class T>
void rd(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  x *= f;
}
const int MAXN = 100100;
int n, m, q, t, tim;
int c[MAXN];
long long ans[MAXN];
set<int> S[MAXN];
set<int>::iterator it, pre, suf;
struct Node {
  int x, y, v, op;
  Node(int x = 0, int y = 0, int v = 0, int op = 0)
      : x(x), y(y), v(v), op(op) {}
  bool operator<(const Node &b) const {
    return x == b.x ? y == b.y ? op < b.op : y < b.y : x > b.x;
  }
} p[MAXN << 3], _p[MAXN << 3];
struct BinaryIndexTree {
  long long sum[MAXN], tag[MAXN];
  void Update(int x, int v) {
    x++;
    for (int y = x; y < MAXN; y += y & -y)
      if (tag[y] != tim)
        tag[y] = tim, sum[y] = v;
      else
        sum[y] += v;
  }
  long long Query(int x) {
    x++;
    long long rnt = 0;
    for (int y = x; y; y -= y & -y)
      if (tag[y] == tim) rnt += sum[y];
    return rnt;
  }
} bit;
void CDQ(int l, int r) {
  if (l + 1 == r) return;
  int mid = l + r >> 1;
  CDQ(l, mid), CDQ(mid, r);
  ++tim;
  int t1 = l, t2 = mid, t = l;
  while (t1 < mid || t2 < r) {
    if (t1 < mid && (t2 == r || p[t1] < p[t2])) {
      if (p[t1].op == 0) bit.Update(p[t1].y, p[t1].v);
      _p[t++] = p[t1++];
    } else {
      if (p[t2].op) ans[p[t2].op] += bit.Query(p[t2].y);
      _p[t++] = p[t2++];
    }
  }
  for (int i = (l); i <= (r - 1); ++i) p[i] = _p[i];
}
void Update(int a, int b) {
  int d = c[a];
  it = S[d].find(a);
  pre = suf = it;
  pre--, suf++;
  if (it != S[d].begin()) p[++t] = Node(*pre, a, (*pre) - a, 0);
  if (suf != S[d].end()) p[++t] = Node(a, *suf, a - (*suf), 0);
  if (it != S[d].begin() && suf != S[d].end())
    p[++t] = Node(*pre, *suf, (*suf) - (*pre), 0);
  S[d].erase(it);
  c[a] = b;
  S[b].insert(a);
  it = S[b].find(a);
  pre = suf = it;
  pre--, suf++;
  if (it != S[b].begin() && suf != S[b].end())
    p[++t] = Node(*pre, *suf, (*pre) - (*suf), 0);
  if (it != S[b].begin()) p[++t] = Node(*pre, a, a - (*pre), 0);
  if (suf != S[b].end()) p[++t] = Node(a, *suf, (*suf) - a, 0);
}
int main() {
  rd(n), rd(m);
  for (int i = (1); i <= (n); ++i) rd(c[i]), S[c[i]].insert(i);
  for (int i = (1); i <= (n); ++i) {
    it = S[c[i]].find(i);
    if (it != S[c[i]].begin()) {
      int x = *(--it);
      p[++t] = Node(x, i, (i - x), 0);
    }
  }
  while (m--) {
    int op, a, b;
    rd(op), rd(a), rd(b);
    if (op == 1)
      Update(a, b);
    else
      p[++t] = Node(a, b, 0, ++q);
  }
  CDQ(1, t + 1);
  for (int i = (1); i <= (q); ++i) printf("%lld\n", ans[i]);
  return 0;
}
