#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int blk = 320;
int a[N], n, m;
set<int> st[N];
vector<pair<int, int> > blocks[blk];
vector<int> sum[blk];
int nxt(int x) {
  auto it = st[a[x]].find(x);
  it++;
  if (it == st[a[x]].end()) return -1;
  return *it;
}
int b4(int x) {
  auto it = st[a[x]].find(x);
  if (it == st[a[x]].begin()) return -1;
  it--;
  return *it;
}
void build(int idx) {
  if (idx < 0) return;
  int lft = idx * blk;
  int rt = min(lft + blk, n);
  blocks[idx].clear();
  sum[idx].clear();
  for (int i = lft; i < rt; i++) {
    int x = nxt(i);
    if (~x)
      blocks[idx].push_back({x, x - i});
    else
      blocks[idx].push_back({x, 0});
  }
  sort(blocks[idx].begin(), blocks[idx].end());
  int ptr = 0;
  for (int i = lft; i < rt; i++) {
    if (sum[idx].size())
      sum[idx].push_back(sum[idx].back() + blocks[idx][ptr++].second);
    else
      sum[idx].push_back(blocks[idx][ptr++].second);
  }
}
void modify(int p, int x) {
  int rt = nxt(p);
  int lft = b4(p);
  st[a[p]].erase(p);
  if (~lft) build(lft / blk);
  a[p] = x;
  st[a[p]].insert(p);
  lft = b4(p);
  if (~lft) build(lft / blk);
  build(p / blk);
}
long long get_sum(int l, int r, int limit) {
  if (l > r) return 0;
  long long ret = 0;
  for (int i = l; i <= r; i++) {
    int lo = 0, hi = blocks[i].size() - 1;
    while (lo < hi) {
      int md = lo + (hi - lo + 1) / 2;
      if (blocks[i][md].first <= limit)
        lo = md;
      else
        hi = md - 1;
    }
    if (blocks[i][lo].first > limit) continue;
    ret += sum[i][lo];
  }
  return ret;
}
long long get_sum2(int l, int r, int limit) {
  if (l > r) return 0;
  long long ret = 0;
  for (int j = l; j <= r; j++) {
    int x = nxt(j);
    if ((~x) && x <= limit) {
      ret += (x - j);
    }
  }
  return ret;
}
int t, l, r;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i), a[i]--;
    st[a[i]].insert(i);
  }
  for (int i = 0; i * blk < n; i++) build(i);
  while (m--) {
    scanf("%d%d%d", &t, &l, &r);
    l--, r--;
    if (t == 1)
      modify(l, r);
    else {
      int blk_lft = l / blk;
      int blk_rt = r / blk;
      long long out = get_sum(blk_lft + 1, blk_rt - 1, r);
      int lft1 = l;
      int rt1 = min(r, (blk_lft + 1) * blk);
      out += get_sum2(lft1, rt1, r);
      if (blk_lft != blk_rt) {
        out += get_sum2((blk_rt - 1) * blk, r, r);
      }
      printf("%lld\n", out);
    }
  }
  return 0;
}
