#include <bits/stdc++.h>
using namespace std;
struct BinaryIndexedTree {
  long long c[100010];
  inline void update(int x, int k) {
    while (x < 100010) {
      c[x] += k;
      x += x & -x;
    }
  }
  inline long long getsum(int x) {
    long long ans = 0;
    while (x > 0) {
      ans += c[x];
      x -= x & -x;
    }
    return ans;
  }
  void clear(int x) {
    while (x < 100010) {
      c[x] = 0;
      x += x & -x;
    }
  }
} BIT;
struct node {
  int tp, x, y, val;
  bool operator<(node a) const { return x == a.x ? tp < a.tp : x < a.x; }
} q[100010 << 3], tmp[100010 << 3];
int n, m, tot, num, pre[100010];
set<int> st[100010];
long long ans[100010];
void update(int x, int y) {
  set<int>::iterator it, pos;
  if (pre[x] == y) return;
  if (pre[x] != 0) {
    pos = it = st[pre[x]].find(x);
    if (it != st[pre[x]].begin()) {
      it--;
      q[++tot] = node{0, x, *it, *it - x};
      it++;
    }
    pos++;
    if (pos != st[pre[x]].end()) {
      q[++tot] = node{0, *pos, x, x - *pos};
      if (it != st[pre[x]].begin()) {
        it--;
        q[++tot] = node{0, *pos, *it, *pos - *it};
        it++;
      }
    }
    st[pre[x]].erase(it);
  }
  pos = it = st[y].insert(x).first;
  if (it != st[y].begin()) {
    it--;
    q[++tot] = node{0, x, *it, x - *it};
    it++;
  }
  pos++;
  if (pos != st[y].end()) {
    q[++tot] = node{0, *pos, x, *pos - x};
    if (it != st[y].begin()) {
      it--;
      q[++tot] = node{0, *pos, *it, *it - *pos};
      it++;
    }
  }
  pre[x] = y;
}
void query(int id, int l, int r) {
  q[++tot] = node{id, r, r, 1};
  q[++tot] = node{id, r, l - 1, -1};
  q[++tot] = node{id, l - 1, r, -1};
  q[++tot] = node{id, l - 1, l - 1, 1};
}
void cdq(int l, int r) {
  if (r - l < 1) return;
  int mid = (l + r) >> 1;
  cdq(l, mid);
  cdq(mid + 1, r);
  int p1 = l, p2 = mid + 1, p = l;
  while (p1 <= mid && p2 <= r) {
    if (q[p1] < q[p2]) {
      if (q[p1].tp == 0) BIT.update(q[p1].y, q[p1].val);
      tmp[p++] = q[p1++];
    } else {
      if (q[p2].tp) ans[q[p2].tp] += q[p2].val * BIT.getsum(q[p2].y);
      tmp[p++] = q[p2++];
    }
  }
  while (p1 <= mid) tmp[p++] = q[p1++];
  while (p2 <= r) {
    if (q[p2].tp) ans[q[p2].tp] += q[p2].val * BIT.getsum(q[p2].y);
    tmp[p++] = q[p2++];
  }
  for (int i = l; i <= r; i++) {
    q[i] = tmp[i];
    if (q[i].tp == 0) BIT.clear(q[i].y);
  }
}
int main() {
  num = tot = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    update(i, x);
  }
  for (int i = 1; i <= m; i++) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1)
      update(x, y);
    else
      query(++num, x, y);
  }
  cdq(1, tot);
  for (int i = 1; i <= num; i++) printf("%lld\n", ans[i]);
  return 0;
}
