#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50;
inline int rd(register int x = 0, register char ch = getchar(),
              register int f = 0) {
  for (; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-';
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 1) + (x << 3) + ch - 48;
  return f ? -x : x;
}
int n, m, cnt;
int a[N], pre[N], A[N], fr[N];
long long val[N], bit[N];
set<int> Set[N];
struct node {
  int t, x, y, val, op;
} q[N * 4], p[N * 4];
bool cmp(node a, node b) { return a.t < b.t; }
void add(int p, int v) {
  p += 5;
  for (; p <= n + 5; p += p & -p) bit[p] += v;
}
long long ask(int p, long long a = 0) {
  p += 5;
  if (p <= 0) return 0;
  for (; p; p -= p & -p) a += bit[p];
  return a;
}
void cdq(int l, int r) {
  if (l >= r) return;
  int mid = (l + r) >> 1, pl = l, pr = mid + 1, pp = l;
  cdq(l, mid), cdq(mid + 1, r);
  while (pl <= mid && pr <= r) {
    if (q[pl].x <= q[pr].x)
      p[pp] = q[pl++], fr[pp++] = 1;
    else
      p[pp++] = q[pr++];
  }
  while (pl <= mid) p[pp] = q[pl++], fr[pp++] = 1;
  while (pr <= r) p[pp++] = q[pr++];
  for (int pos = l; pos <= r; ++pos) {
    if (fr[pos] && !p[pos].op)
      add(p[pos].y, p[pos].val);
    else if (!fr[pos] && p[pos].op)
      val[p[pos].op] += ask(n) - ask(p[pos].y - 1);
  }
  for (int pos = l; pos <= r; ++pos) {
    q[pos] = p[pos];
    if (fr[pos] && !p[pos].op) add(p[pos].y, -p[pos].val);
    fr[pos] = 0;
  }
}
int main() {
  n = rd(), m = rd();
  for (int i = 1; i <= n; ++i) {
    a[i] = rd();
    if (Set[a[i]].size()) pre[i] = *--Set[a[i]].end();
    Set[a[i]].insert(i);
    q[++cnt] = (node){0, i, pre[i], i - pre[i], 0};
  }
  for (int r = 1; r <= m; ++r) {
    A[r] = rd();
    int b = rd(), c = rd();
    if (A[r] == 1) {
      q[++cnt] = (node){r, b, pre[b], pre[b] - b, 0};
      if (next(Set[a[b]].find(b)) != Set[a[b]].end()) {
        int pos = *next(Set[a[b]].find(b));
        q[++cnt] = (node){r, pos, pre[pos], pre[pos] - pos, 0};
        pre[pos] = pre[b];
        q[++cnt] = (node){r, pos, pre[pos], pos - pre[pos], 0};
      }
      Set[a[b]].erase(b);
      a[b] = c;
      pre[b] = 0;
      Set[a[b]].insert(b);
      if (Set[a[b]].find(b) != Set[a[b]].begin())
        pre[b] = *prev(Set[a[b]].find(b));
      q[++cnt] = (node){r, b, pre[b], b - pre[b], 0};
      if (next(Set[a[b]].find(b)) != Set[a[b]].end()) {
        int pos = *next(Set[a[b]].find(b));
        q[++cnt] = (node){r, pos, pre[pos], pre[pos] - pos, 0};
        pre[pos] = b;
        q[++cnt] = (node){r, pos, pre[pos], pos - pre[pos], 0};
      }
    } else
      q[++cnt] = (node){r, c, b, 0, r};
  }
  cdq(1, cnt);
  for (int i = 1; i <= m; ++i)
    if (A[i] == 2) printf("%lld\n", val[i]);
}
