#include <bits/stdc++.h>
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
using namespace std;
const int N = 1e5 + 7, inf = 1e9 + 7, mod = 1e9 + 7;
const long long linf = (long long)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1},
          dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int get_int() {
  char x = getchar();
  bool mns = 0;
  while (!isdigit(x)) mns |= x == '-', x = getchar();
  int res = 0;
  while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
  if (mns) res = -res;
  return res;
}
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
}
int mult(int x, int y) { return x * 1ll * y % mod; }
int sum(int x, int y) {
  add(x, y);
  return x;
}
int n, m;
int a[N];
int pr[N], nx[N], bfr[N];
struct node {
  node *l, *r;
  int x, y, val;
  long long sum;
  node(int prv = 0, int id = 0) {
    l = r = 0;
    sum = val = id;
    x = prv;
    y = rand();
  }
};
struct treap {
  node *t;
  long long gs(node *&v) { return v ? v->sum : 0; }
  void rc(node *&v) {
    if (v) v->sum = gs(v->l) + gs(v->r) + v->val;
  }
  void split(node *&t, node *&l, node *&r, int x) {
    if (!t) {
      l = r = 0;
      return;
    }
    if (t->x <= x) {
      l = t;
      split(t->r, t->r, r, x);
    } else {
      r = t;
      split(t->l, l, t->l, x);
    }
    rc(t);
  }
  node *merge(node *l, node *r) {
    if (!l || !r) return l ? l : r;
    if (l->y >= r->y) {
      l->r = merge(l->r, r);
      rc(l);
      rc(r);
      return l;
    } else {
      r->l = merge(l, r->l);
      rc(r);
      rc(l);
      return r;
    }
  }
  void insert(int prv, int id) {
    node *L, *R;
    split(t, L, R, prv);
    L = merge(L, new node(prv, id));
    t = merge(L, R);
  }
  void erase(int prv) {
    node *L, *R, *M;
    split(t, L, R, prv);
    split(L, L, M, prv - 1);
    t = merge(L, R);
  }
  long long get(int x) {
    node *L, *R;
    split(t, L, R, x - 1);
    long long res = gs(R);
    t = merge(L, R);
    return res;
  }
} first[N];
void add(int p, int prv, int id) {
  for (; p < N; p |= p + 1) first[p].insert(prv, id);
}
void del(int p, int prv) {
  for (; p < N; p |= p + 1) first[p].erase(prv);
}
long long get(int p, int L) {
  long long res = 0;
  for (; p >= 0; p = (p & (p + 1)) - 1) res += first[p].get(L);
  return res;
}
set<int> pos[N];
void solve() {
  n = get_int(), m = get_int();
  for (int i = 1; i <= n; i++) {
    a[i] = get_int();
    pos[a[i]].insert(i);
    pr[i] = bfr[a[i]];
    bfr[a[i]] = i;
    if (pr[i]) add(i, pr[i], i - pr[i]);
  }
  for (int i = 1; i <= n; i++) bfr[i] = 0;
  for (int i = n; i >= 1; i--) {
    nx[i] = bfr[a[i]];
    bfr[a[i]] = i;
  }
  for (int i = 1; i <= m; i++) {
    int type = get_int(), l = get_int(), r = get_int();
    if (type == 1) {
      if (a[l] == r) continue;
      if (pr[l]) {
        del(l, pr[l]);
        nx[pr[l]] = nx[l];
      }
      pos[a[l]].erase(l);
      a[l] = r;
      pos[a[l]].insert(l);
      if (nx[l]) {
        del(nx[l], l);
        pr[nx[l]] = pr[l];
        if (pr[l]) add(nx[l], pr[l], nx[l] - pr[l]);
      }
      auto it = pos[r].upper_bound(l);
      if (it != pos[r].end()) {
        nx[l] = *it;
        if (pr[nx[l]]) del(nx[l], pr[nx[l]]);
        pr[nx[l]] = l;
        add(nx[l], pr[nx[l]], nx[l] - l);
      } else
        nx[l] = 0;
      it = pos[r].lower_bound(l);
      if (it == pos[r].begin()) {
        if (pr[l]) del(l, pr[l]);
        pr[l] = 0;
      } else {
        if (pr[l]) del(l, pr[l]);
        pr[l] = *--it;
        add(l, pr[l], l - pr[l]);
      }
    } else
      printf("%I64d\n", get(r, l));
  }
}
int main() {
  int t = 1;
  while (t--) solve();
  exit(0);
}
