#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
set<int> st[N];
set<int>::iterator it;
int n, q, m, idd, c[N];
int pre[N], nxt[N];
long long ans[N];
struct opes {
  int op, x, y, val, id;
} nd[N];
bool chk(int x) { return x && x != n + 1; }
void calc(int p, int las) {
  if (chk(p) && chk(pre[p])) nd[++m] = (opes){0, p, pre[p], -(p - pre[p]), 0};
  if (chk(p)) pre[p] = las;
  if (chk(las)) nxt[las] = p;
  if (chk(p) && chk(pre[p])) nd[++m] = (opes){0, p, pre[p], +(p - pre[p]), 0};
}
int getnxt(int x) {
  it = st[c[x]].find(x);
  it++;
  return *it;
}
int getpre(int x) {
  it = st[c[x]].find(x);
  it--;
  return *it;
}
struct bit {
  long long sum[N];
  int lowbit(int x) { return x & (-x); }
  void update(int x, int a) {
    if (!x || !a) return;
    for (; x <= n; x += lowbit(x)) sum[x] += a;
  }
  long long query(int x) {
    if (!x) return 0;
    long long res = 0;
    for (; x; x -= lowbit(x)) res += sum[x];
    return res;
  }
  long long gao(int x) { return query(n) - query(x - 1); }
} bit;
bool cmpx(opes a, opes b) { return a.x < b.x; }
void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  cdq(l, mid);
  cdq(mid + 1, r);
  int long long = l;
  for (int i = (mid + 1); i < (r + 1); i++)
    if (nd[i].op == 1) {
      while (long long <= mid && nd[long long].x <= nd[i].x) {
        if (!nd[long long].op) bit.update(nd[long long].y, nd[long long].val);
        long long ++;
      }
      ans[nd[i].id] += bit.gao(nd[i].y);
    }
  for (int i = (l); i < (long long); i++)
    if (!nd[i].op) bit.update(nd[i].y, -nd[i].val);
  inplace_merge(nd + l, nd + mid + 1, nd + r + 1, cmpx);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = (1); i < (n + 1); i++) st[i].insert(0), st[i].insert(n + 1);
  for (int i = (1); i < (n + 1); i++) {
    scanf("%d", &c[i]);
    st[c[i]].insert(i);
  }
  for (int i = (1); i < (n + 1); i++) {
    pre[i] = getpre(i);
    nxt[i] = getnxt(i);
    if (pre[i]) nd[++m] = (opes){0, i, pre[i], i - pre[i], 0};
  }
  for (int i = (1); i < (q + 1); i++) {
    int op, a, b;
    scanf("%d%d%d", &op, &a, &b);
    if (op == 2)
      nd[++m] = (opes){1, b, a, 0, ++idd};
    else {
      st[c[a]].erase(a);
      c[a] = b;
      st[c[a]].insert(a);
      int t1 = pre[a], t2 = nxt[a];
      calc(t2, t1);
      t1 = getpre(a), t2 = getnxt(a);
      calc(t2, a), calc(a, t1);
    }
  }
  cdq(1, m);
  for (int i = (1); i < (idd + 1); i++) printf("%lld\n", ans[i]);
  return 0;
}
