#include <bits/stdc++.h>
struct query {
  bool t;
  int x, y;
};
class bit {
  int n;
  std::vector<long long> b;

 public:
  void resize(int size) {
    n = size;
    b.resize(n);
  }
  void add(int i, int x) {
    while (i < n) {
      b[i] += x;
      i |= i + 1;
    }
  }
  long long get(int i) {
    long long s = 0;
    while (i >= 0) {
      s += b[i];
      i = (i & i + 1) - 1;
    }
    return s;
  }
  long long sum(int l, int r) { return get(r) - get(l - 1); }
};
const int N = 100000;
const int T = 262143;
int n, m, a[N], copy[N];
query q[N];
std::set<int> s[N];
std::vector<int> val[T][2];
bit t[T][2];
void add(int i, bool b, int x, int v = 0, int tl = 0, int tr = n) {
  val[v][b].push_back(x);
  if (tr - tl != 1) {
    int m = (tl + tr) >> 1;
    if (i < m)
      add(i, b, x, (v << 1) + 1, tl, m);
    else
      add(i, b, x, (v << 1) + 2, m, tr);
  }
}
void build(int v = 0, int tl = 0, int tr = n) {
  val[v][0].push_back(-1);
  val[v][1].push_back(n);
  for (int i, j, k = 0; k < 2; ++k) {
    std::sort(val[v][k].begin(), val[v][k].end());
    for (i = 0, j = 0; i < (int)val[v][k].size(); ++j) {
      val[v][k][j] = val[v][k][i];
      do {
        ++i;
      } while (i < (int)val[v][k].size() && val[v][k][i] == val[v][k][j]);
    }
    val[v][k].resize(j);
    t[v][k].resize(j);
  }
  if (tr - tl != 1) {
    int m = (tl + tr) >> 1;
    build((v << 1) + 1, tl, m);
    build((v << 1) + 2, m, tr);
  }
}
void update(int i, bool b, int p, int d, int v = 0, int tl = 0, int tr = n) {
  t[v][b].add(std::lower_bound(val[v][b].begin(), val[v][b].end(), p) -
                  val[v][b].begin(),
              d);
  if (tr - tl != 1) {
    int m = (tl + tr) >> 1;
    if (i < m)
      update(i, b, p, d, (v << 1) + 1, tl, m);
    else
      update(i, b, p, d, (v << 1) + 2, m, tr);
  }
}
long long query(int l, int r, int v = 0, int tl = 0, int tr = n) {
  if (tl >= r || tr <= l) return 0;
  if (tl >= l && tr <= r)
    return t[v][1].sum(std::lower_bound(val[v][1].begin(), val[v][1].end(), r) -
                           val[v][1].begin(),
                       (int)val[v][1].size() - 1) -
           t[v][0].sum(0,
                       std::lower_bound(val[v][0].begin(), val[v][0].end(), l) -
                           val[v][0].begin() - 1);
  int m = (tl + tr) >> 1;
  return query(l, r, (v << 1) + 1, tl, m) + query(l, r, (v << 1) + 2, m, tr);
}
void modify(int i, int x, int pr, bool prep, bool rem) {
  std::set<int>::iterator it;
  if (rem) {
    it = s[pr].find(i);
    if (it == s[pr].begin()) {
      if (!prep) update(i, 0, -1, -i);
    } else {
      if (!prep) {
        update(i, 0, *prev(it), -i);
        update(*prev(it), 1, i, -*prev(it));
      }
      if (next(it) != s[pr].end()) {
        if (prep) {
          add(*prev(it), 1, *next(it));
          add(*next(it), 0, *prev(it));
        } else {
          update(*prev(it), 1, *next(it), *prev(it));
          update(*next(it), 0, *prev(it), *next(it));
        }
      } else if (!prep)
        update(*prev(it), 1, n, *prev(it));
    }
    if (!prep) {
      if (next(it) == s[pr].end())
        update(i, 1, n, -i);
      else {
        update(i, 1, *next(it), -i);
        update(*next(it), 0, i, -*next(it));
        if (it == s[pr].begin()) update(*next(it), 0, -1, *next(it));
      }
    }
    s[pr].erase(it);
  }
  it = s[x].upper_bound(i);
  if (it == s[x].begin()) {
    if (!prep) update(i, 0, -1, i);
  } else {
    if (prep) {
      add(i, 0, *prev(it));
      add(*prev(it), 1, i);
    } else {
      update(*prev(it), 1, it == s[x].end() ? n : *it, -*prev(it));
      update(*prev(it), 1, i, *prev(it));
      update(i, 0, *prev(it), i);
    }
  }
  if (it == s[x].end()) {
    if (!prep) update(i, 1, n, i);
  } else {
    if (prep) {
      add(i, 1, *it);
      add(*it, 0, i);
    } else {
      update(*it, 0, it == s[x].begin() ? -1 : *prev(it), -*it);
      update(*it, 0, i, *it);
      update(i, 1, *it, i);
    }
  }
  s[x].insert(i);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    --a[i];
    modify(i, a[i], 0, true, false);
  }
  memcpy(copy, a, n << 2);
  for (int i = 0; i < m; ++i) {
    int buf;
    scanf("%d%d%d", &buf, &q[i].x, &q[i].y);
    q[i].t = buf - 1;
    --q[i].x;
    --q[i].y;
    if (!q[i].t) {
      modify(q[i].x, q[i].y, copy[q[i].x], true, true);
      copy[q[i].x] = q[i].y;
    }
  }
  build();
  for (int i = 0; i < n; ++i) s[i].clear();
  for (int i = 0; i < n; ++i) modify(i, a[i], 0, false, false);
  for (int i = 0; i < m; ++i) {
    if (q[i].t)
      printf("%lld\n", query(q[i].x, q[i].y + 1));
    else {
      modify(q[i].x, q[i].y, a[q[i].x], false, true);
      a[q[i].x] = q[i].y;
    }
  }
  return 0;
}
