#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 9;
const int POT = 1 << 17;
int tab[MAXN];
set<int> lista[MAXN];
class PointerST {
 private:
  struct Vertex {
    int left;
    int right;
    unsigned int val;
    Vertex() : left(0), right(0), val(0) {}
  };
  static const int POT2 = 1 << 17;
  vector<Vertex> vec;

 public:
  PointerST();
  void add(int, int);
  unsigned int query(int, int);
  void addR(int, int, int, int, int);
  unsigned int queryR(int, int, int, int, int);
} st[POT + POT];
;
PointerST::PointerST() { vec.push_back(Vertex()); }
void PointerST::add(int a, int x) {
  addR(0, POT2, POT2 + POT2 - 1, a + POT2, x);
}
unsigned int PointerST::query(int a, int b) {
  return queryR(0, POT2, POT2 + POT2 - 1, a + POT2, b + POT2);
}
void PointerST::addR(int poz, int p, int k, int a, int x) {
  if ((p == a) && (k == a)) {
    vec[poz].val = x;
    return;
  }
  int mid = p + k;
  mid /= 2;
  if (mid >= a) {
    if (vec[poz].left == 0) {
      vec[poz].left = ((int)vec.size());
      vec.push_back(Vertex());
    }
    addR(vec[poz].left, p, mid, a, x);
  } else {
    if (vec[poz].right == 0) {
      vec[poz].right = ((int)vec.size());
      vec.push_back(Vertex());
    }
    addR(vec[poz].right, mid + 1, k, a, x);
  }
  vec[poz].val = vec[vec[poz].left].val + vec[vec[poz].right].val;
}
unsigned int PointerST::queryR(int poz, int p, int k, int a, int b) {
  if ((p == a) && (b == k)) return vec[poz].val;
  unsigned int wyn = 0;
  int mid = p + k;
  mid /= 2;
  if (mid >= a)
    if (vec[poz].left != 0)
      wyn += queryR(vec[poz].left, p, mid, a, min(b, mid));
  if (mid < b)
    if (vec[poz].right != 0)
      wyn += queryR(vec[poz].right, mid + 1, k, max(a, mid + 1), b);
  return wyn;
}
void add(int a, int nxt, int x) {
  a += POT;
  st[a].add(nxt, x);
  a /= 2;
  while (a > 0) {
    st[a].add(nxt, x);
    a /= 2;
  }
}
unsigned int query(int a, int b) {
  unsigned int wyn = 0;
  int sup = b;
  a += POT - 1;
  b += POT + 1;
  while (a + 1 != b) {
    if (a % 2 == 0) wyn += st[a + 1].query(1, sup);
    if (b % 2 == 1) wyn += st[b - 1].query(1, sup);
    a /= 2;
    b /= 2;
  }
  return wyn;
}
void update(int p, int x) {
  if (tab[p - 1] == x) return;
  int old = tab[p - 1];
  tab[p - 1] = x;
  auto it = lista[old].find(p - 1);
  auto pop = it;
  auto nxt = it;
  nxt++;
  if (nxt != lista[old].end()) add(*it + 1, *nxt + 1, 0);
  if (it != lista[old].begin()) {
    pop--;
    add(*pop + 1, *it + 1, 0);
    if (nxt != lista[old].end()) add(*pop + 1, *nxt + 1, *nxt - *pop);
  }
  lista[x].insert(p - 1);
  lista[old].erase(p - 1);
  it = lista[x].find(p - 1);
  if (it == lista[x].begin()) {
    nxt = it;
    nxt++;
    if (nxt != lista[x].end()) add(*it + 1, *nxt + 1, *nxt - *it);
  } else {
    nxt = it;
    nxt++;
    pop = it;
    pop--;
    if (nxt == lista[x].end())
      add(*pop + 1, *it + 1, *it - *pop);
    else {
      add(*pop + 1, *nxt + 1, 0);
      add(*pop + 1, *it + 1, *it - *pop);
      add(*it + 1, *nxt + 1, *nxt - *it);
    }
  }
}
int main() {
  int n, m, a, b, c;
  cin >> n >> m;
  for (int i = 0; i < (n); ++i) {
    scanf("%d", &tab[i]);
    lista[tab[i]].insert(i);
  }
  auto it2 = lista[0].begin();
  for (int i = 0; i < (n + 1); ++i) {
    for (auto it = lista[i].begin(); it != lista[i].end(); it++) {
      if (it == lista[i].begin()) {
        it2 = it;
        continue;
      }
      add(*it2 + 1, *it + 1, *it - *it2);
      it2 = it;
    }
  }
  for (int i = 0; i < (m); ++i) {
    scanf("%d %d %d", &a, &b, &c);
    if (a == 2)
      printf("%u\n", query(b, c));
    else
      update(b, c);
  }
  return 0;
}
