#include <bits/stdc++.h>
using namespace std;
const int MAX = 120010;
set<int> sota[MAX];
set<int>::iterator it;
int ara[MAX], blockSz, n;
pair<int, long long> org[MAX];
struct Node {
  int p;
  pair<int, long long> val[320];
} block[320];
int which(int p) { return (p / blockSz); }
int shuru(int bid) { return bid * blockSz; }
int sesh(int bid) { return (bid + 1) * blockSz - 1; }
void update(int bId) {
  for (int i = 0; i <= 319; i++) block[bId].val[i] = {-1, 0};
  int l = shuru(bId), r = min(n, sesh(bId));
  int &p = block[bId].p;
  p = 0;
  for (int i = l; i <= r; i++, p++) {
    int x = ara[i];
    it = sota[x].lower_bound(i);
    if (!sota[x].empty() && it != sota[x].begin()) {
      it--;
      int prvPos = *it;
      block[bId].val[p].first = prvPos;
      block[bId].val[p].second = i - prvPos;
    } else
      block[bId].val[p] = {-1, 0};
    org[i] = block[bId].val[p];
  }
  sort(block[bId].val, block[bId].val + p);
  for (int i = 0; i <= p; i++)
    block[bId].val[i].second += block[bId].val[i - 1].second;
}
void del(int p) {
  int x = ara[p];
  sota[x].erase(p);
  it = sota[x].upper_bound(p);
  if (!sota[x].empty() && it != sota[x].end()) {
    int nexPos = *it;
    update(which(nexPos));
  }
}
void add(int p) {
  int x = ara[p];
  sota[x].insert(p);
  it = sota[x].upper_bound(p);
  if (!sota[x].empty() && it != sota[x].end()) {
    int nexPos = *it;
    update(which(nexPos));
  }
  update(which(p));
}
long long query(int l, int r) {
  long long ret = 0;
  for (int i = l; i <= r; i++) {
    int bid = which(i);
    int fo = shuru(bid), so = sesh(bid);
    if (l <= fo && so <= r) {
      int &p = block[bid].p;
      int st = 0, en = p - 1, avv = p, mid;
      while (st <= en) {
        mid = (st + en) >> 1;
        if (block[bid].val[mid].first < l)
          st = mid + 1;
        else
          en = mid - 1, avv = min(p, mid);
      }
      if (avv != p) {
        ret += block[bid].val[p].second;
        if (avv) ret -= block[bid].val[avv - 1].second;
      }
      i = so;
    } else if (org[i].first >= l)
      ret += org[i].second;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  int ty, p, x, l, r, q;
  cin >> n >> q;
  blockSz = sqrt(n) + 1;
  for (int i = 0; i <= n - 1; i++) {
    cin >> ara[i];
    sota[ara[i]].insert(i);
  }
  for (int i = 0; i <= n - 1; i++)
    if (!i || which(i) != which(i - 1)) update(which(i));
  for (int i = 0; i <= q - 1; i++) {
    cin >> ty;
    if (ty == 1) {
      cin >> p >> x;
      p--;
      del(p);
      ara[p] = x;
      add(p);
    } else {
      cin >> l >> r;
      l--;
      r--;
      cout << query(l, r) << endl;
    }
  }
  return 0;
}
