#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int a[MAXN], op[MAXN], op1[MAXN], op2[MAXN];
int n, m;
vector<long long> sum[MAXN * 4];
set<int> col[MAXN];
vector<int> e[MAXN * 4];
void get(int o, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    e[o].push_back(x);
    return;
  }
  int mid = (l + r) / 2, lch = o * 2, rch = lch + 1;
  if (mid >= x) get(lch, l, mid, x, y);
  if (mid < y) get(rch, mid + 1, r, x, y);
}
void build(int o, int l, int r) {
  if (e[o].size()) {
    sort(e[o].begin(), e[o].end());
    int sz = unique(e[o].begin(), e[o].end()) - e[o].begin();
    for (int i = 0; i <= sz; i++) sum[o].push_back(0);
  }
  if (l == r) return;
  int mid = (l + r) / 2, lch = o * 2, rch = lch + 1;
  build(lch, l, mid);
  build(rch, mid + 1, r);
}
void add(int o, int x, int v) {
  while (x) {
    sum[o][x] += v;
    x -= (x & -x);
  }
}
long long getsum(int o, int x) {
  long long res = 0;
  while (x < sum[o].size()) {
    res += sum[o][x];
    x += (x & -x);
  }
  return res;
}
void update(int o, int l, int r, int x, int p, int v) {
  if (sum[o].size()) {
    int pos = upper_bound(e[o].begin(), e[o].begin() + sum[o].size() - 1, p) -
              e[o].begin();
    if (pos != 0) add(o, pos, v);
  }
  if (l == r) return;
  int mid = (l + r) / 2, lch = o * 2, rch = lch + 1;
  if (mid >= x)
    update(lch, l, mid, x, p, v);
  else
    update(rch, mid + 1, r, x, p, v);
}
long long res;
void query(int o, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    res += getsum(
        o, lower_bound(e[o].begin(), e[o].begin() + sum[o].size() - 1, x) -
               e[o].begin() + 1);
    return;
  }
  int mid = (l + r) / 2, lch = o * 2, rch = lch + 1;
  if (mid >= x) query(lch, l, mid, x, y);
  if (mid < y) query(rch, mid + 1, r, x, y);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    col[a[i]].insert(i);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &op[i], &op1[i], &op2[i]);
    if (op[i] == 2) get(1, 1, n, op1[i], op2[i]);
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    auto pos = col[a[i]].lower_bound(i);
    if (pos == col[a[i]].begin()) continue;
    pos--;
    update(1, 1, n, i, *pos, i - *pos);
  }
  for (int i = 1; i <= m; i++) {
    if (op[i] == 1) {
      int x = op1[i], v = op2[i];
      if (a[x] == v) continue;
      auto pos = col[a[x]].lower_bound(x);
      int flag = 0;
      if (pos != col[a[x]].begin()) {
        pos--;
        flag++;
        update(1, 1, n, x, *pos, *pos - x);
      }
      pos = col[a[x]].lower_bound(x);
      pos++;
      if (pos != col[a[x]].end()) {
        flag++;
        update(1, 1, n, *pos, x, x - *pos);
      }
      if (flag == 2) {
        pos = col[a[x]].lower_bound(x);
        auto ppos = pos;
        ppos--;
        pos++;
        update(1, 1, n, *pos, *ppos, *pos - *ppos);
      }
      col[a[x]].erase(x);
      a[x] = v;
      col[v].insert(x);
      pos = col[v].lower_bound(x);
      flag = 0;
      if (pos != col[v].begin()) {
        pos--;
        flag++;
        update(1, 1, n, x, *pos, x - *pos);
      }
      pos = col[v].lower_bound(x);
      pos++;
      if (pos != col[a[x]].end()) {
        flag++;
        update(1, 1, n, *pos, x, *pos - x);
      }
      if (flag == 2) {
        pos = col[v].lower_bound(x);
        auto ppos = pos;
        ppos--;
        pos++;
        update(1, 1, n, *pos, *ppos, *ppos - *pos);
      }
    } else {
      res = 0;
      query(1, 1, n, op1[i], op2[i]);
      printf("%I64d\n", res);
    }
  }
}
