#include <bits/stdc++.h>
using namespace std;
long long n, k, x, a[100100], pre[100100], m, nxt[100100], t, y;
string s;
set<long long> pos[100100];
template <class T>
ostream &operator<<(ostream &out, vector<T> v) {
  out << v.size() << '\n';
  for (auto e : v) out << e << ' ';
  return out;
}
struct tr {
  long long k, p, s, v;
  tr *l, *r;
  tr(long long _k, long long _v) {
    s = v = _v;
    k = _k;
    p = rand();
    r = l = NULL;
  }
};
void upd(tr *t) {
  if (!t) return;
  t->s = t->v;
  if (t->l) t->s += t->l->s;
  if (t->r) t->s += t->r->s;
}
void split(tr *rt, long long key, tr *&l, tr *&r) {
  if (rt == NULL)
    l = r = NULL;
  else if (key < rt->k)
    split(rt->l, key, l, rt->l), r = rt;
  else
    split(rt->r, key, rt->r, r), l = rt;
  upd(rt);
}
void merge(tr *&rt, tr *l, tr *r) {
  if (!l || !r)
    rt = l ? l : r;
  else if (l->p > r->p)
    merge(l->r, l->r, r), rt = l;
  else
    merge(r->l, l, r->l), rt = r;
  upd(rt);
}
void insert(tr *&rt, long long key, long long val) {
  tr *e, *l, *r;
  split(rt, key, l, r);
  split(l, key - 1, l, e);
  if (e == NULL)
    e = new tr(key, val);
  else
    e->v += val;
  upd(e);
  merge(l, l, e);
  merge(rt, l, r);
}
void remove(tr *&rt, long long key, long long val) {
  tr *e, *l, *r;
  split(rt, key, l, r);
  split(l, key - 1, l, e);
  if (e != NULL) e->v -= val;
  upd(e);
  if (!e || e->v > 0) merge(l, l, e);
  merge(rt, l, r);
}
tr *st[4 * 100100];
void build(long long node, long long l, long long r) {
  if (l == r) {
    if (pre[l])
      st[node] = new tr(pre[l], l - pre[l]);
    else
      st[node] = NULL;
    return;
  }
  long long mid = (l + r) / 2;
  build(2 * node, l, mid);
  build(2 * node + 1, mid + 1, r);
  st[node] = NULL;
  for (long long i = l; i <= r; i++)
    if (pre[i]) insert(st[node], pre[i], i - pre[i]);
}
void update(long long node, long long l, long long r, long long pos,
            long long oldpre) {
  ;
  ;
  ;
  if (l == r) {
    st[node] = new tr(pre[pos], pos - pre[pos]);
    return;
  }
  long long mid = (l + r) / 2;
  if (pos <= mid)
    update(2 * node, l, mid, pos, oldpre);
  else
    update(2 * node + 1, mid + 1, r, pos, oldpre);
  remove(st[node], oldpre, pos - oldpre);
  insert(st[node], pre[pos], pos - pre[pos]);
}
long long query(long long node, long long l, long long r, long long x,
                long long y) {
  if (y < l || x > r) return 0;
  if (x <= l && r <= y) {
    ;
    ;
    tr *l, *r;
    split(st[node], x - 1, l, r);
    long long ans = r ? r->s : 0;
    merge(st[node], l, r);
    ;
    return ans;
  }
  long long mid = (l + r) / 2;
  long long ans = 0;
  if (x <= mid) ans += query(2 * node, l, mid, x, y);
  if (y > mid) ans += query(2 * node + 1, mid + 1, r, x, y);
  return ans;
}
long long getPre(long long i) {
  auto it = pos[a[i]].lower_bound(i);
  if (it != pos[a[i]].begin()) {
    it--;
    return *it;
  }
  return 0;
}
long long getNxt(long long i) {
  auto it = pos[a[i]].upper_bound(i);
  if (it != pos[a[i]].end()) return *it;
  return 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
    pos[a[i]].insert(i);
    pre[i] = getPre(i);
    if (pre[i]) nxt[pre[i]] = i;
  }
  build(1, 1, n);
  for (long long i = 1; i <= m; i++) {
    cin >> t >> x >> y;
    if (t == 1) {
      long long p = x, opn;
      long long prei = pre[p], nxti = nxt[p], k = y;
      if (a[p] == y) continue;
      pos[a[p]].erase(p);
      pos[k].insert(p);
      a[p] = k;
      pre[nxti] = prei;
      nxt[prei] = nxti;
      pre[p] = getPre(p);
      if (pre[p]) nxt[pre[p]] = p;
      nxt[p] = getNxt(p);
      if (nxt[p]) opn = pre[nxt[p]], pre[nxt[p]] = p;
      pre[0] = nxt[0] = 0;
      update(1, 1, n, p, prei);
      if (nxti) update(1, 1, n, nxti, p);
      if (nxt[p]) update(1, 1, n, nxt[p], opn);
    } else
      cout << query(1, 1, n, x, y) << '\n';
  }
  return 0;
}
