#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
int n, m;
int a[N], root[N];
int ls[M], rs[M], tot = 0;
long long sum[M];
set<int> s[N];
const int inf = 1e9;
void update(int &x, int l, int r, int pos, int val) {
  if (!x) x = ++tot;
  sum[x] += val;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(ls[x], l, mid, pos, val);
  else
    update(rs[x], mid + 1, r, pos, val);
}
long long query(int x, int l, int r, int L, int R) {
  if (!x || (L == l && R == r)) return sum[x];
  int mid = (l + r) >> 1;
  if (R <= mid)
    return query(ls[x], l, mid, L, R);
  else if (L > mid)
    return query(rs[x], mid + 1, r, L, R);
  else
    return query(ls[x], l, mid, L, mid) + query(rs[x], mid + 1, r, mid + 1, R);
}
void update(int x, int y, int v) {
  for (; x <= n; x += x & -x) update(root[x], 1, n, y, v);
}
long long query(int x, int l, int r) {
  long long ans = 0;
  for (; x; x -= x & -x) ans += query(root[x], 1, n, l, r);
  return ans;
}
long long query(int x, int y) { return query(y, x, y) - query(x - 1, x, y); }
void solve(int v, int p, int fl) {
  if (fl == -1) s[v].erase(p);
  int nxt = *s[v].lower_bound(p);
  int pre = *(--s[v].lower_bound(p));
  if (nxt <= n) update(nxt, p, fl * (nxt - p));
  if (pre >= 1) update(p, pre, fl * (p - pre));
  if (nxt <= n && pre >= 1) update(nxt, pre, fl * (pre - nxt));
  if (fl == 1) s[v].insert(p);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i(1); i <= (n); ++i) s[i].insert(-1e9), s[i].insert(1e9);
  for (int i(1); i <= (n); ++i) {
    scanf("%d", a + i);
    solve(a[i], i, 1);
  }
  for (int i(1); i <= (m); ++i) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 2)
      printf("%lld\n", query(x, y));
    else {
      solve(a[x], x, -1);
      solve(a[x] = y, x, 1);
    }
  }
  return 0;
}
