#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 4;
const int inf = 0x3f3f3f3f;
int lson[maxn * 100], rson[maxn * 100], rt[maxn];
long long sum[maxn * 100];
int n, m, sz, a[maxn];
set<int> s[maxn];
void PushUp(int i) { sum[i] = sum[lson[i]] + sum[rson[i]]; }
void insert(int &rt, int l, int r, int k, long long val) {
  if (!rt) rt = ++sz;
  int mid = l + r >> 1;
  if (l == r) {
    sum[rt] += val;
    return;
  }
  if (k <= mid)
    insert(lson[rt], l, mid, k, val);
  else
    insert(rson[rt], mid + 1, r, k, val);
  PushUp(rt);
}
long long query(int rt, int l, int r, int L, int R) {
  if (!rt || L <= l && r <= R) return sum[rt];
  int mid = l + r >> 1;
  long long res = 0;
  if (L <= mid) res += query(lson[rt], l, mid, L, R);
  if (mid < R) res += query(rson[rt], mid + 1, r, L, R);
  return res;
}
void BIT_ins(int x, int k, long long val) {
  while (x <= n) {
    insert(rt[x], 1, n, k, val);
    x += x & (-x);
  }
}
long long BIT_query(int x, int l, int r) {
  long long res = 0;
  while (x) {
    res += query(rt[x], 1, n, l, r);
    x -= x & (-x);
  }
  return res;
}
void ins(int x, int w) {
  s[x].insert(w);
  bool flag1 = false, flag2 = false;
  set<int>::iterator it = s[x].find(w), pre = it, nxt = it;
  pre--;
  nxt++;
  if (it != s[x].begin()) {
    BIT_ins(*pre, w, w - *pre);
    flag1 = true;
  }
  if (nxt != s[x].end()) {
    BIT_ins(w, *nxt, *nxt - w);
    flag2 = true;
  }
  if (flag1 && flag2) BIT_ins(*pre, *nxt, (long long)(*pre - *nxt));
}
void del(int x, int w) {
  bool flag1 = false, flag2 = false;
  set<int>::iterator it = s[x].find(w), pre = it, nxt = it;
  pre--;
  nxt++;
  if (it != s[x].begin()) {
    BIT_ins(*pre, w, *pre - w);
    flag1 = true;
  }
  if (nxt != s[x].end()) {
    BIT_ins(w, *nxt, w - *nxt);
    flag2 = true;
  }
  if (flag1 && flag2) BIT_ins(*pre, *nxt, (long long)(*nxt - *pre));
  s[x].erase(w);
}
int main() {
  sz = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    ins(a[i], i);
  }
  while (m--) {
    int st, l, r;
    scanf("%d%d%d", &st, &l, &r);
    if (st == 1) {
      del(a[l], l);
      a[l] = r;
      ins(a[l], l);
    } else
      printf("%I64d\n", BIT_query(n, l, r) - BIT_query(l - 1, l, r));
  }
  return 0;
}
