#include <bits/stdc++.h>
using namespace std;
int n;
int m;
vector<int> v;
vector<pair<pair<int, int>, int> > vv;
vector<pair<int, int> > query[100003];
long long int bit[100003];
void add(int i, int x) {
  i++;
  while (i < 100003) {
    bit[i] += x;
    i += i & -i;
  }
}
long long int sum(int i) {
  long long int r = 0;
  i++;
  while (i) {
    r += bit[i];
    i -= i & -i;
  }
  return r;
}
int pr[100003];
long long int ans[100003];
int mint[100003];
int maxt[100003];
vector<pair<int, int> > vals;
set<int> tmps;
vector<int> ap[100003];
int us[100003];
int us2[100003];
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
  return a.second < b.second;
}
bool cmp2(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }
int cc[100003];
int sz[100003];
int read_int() {
  int num = 0;
  while (1) {
    char c = getchar();
    if (!isdigit(c)) {
      continue;
    }
    num += c - '0';
    break;
  }
  while (1) {
    char c = getchar();
    if (!isdigit(c)) {
      return num;
    }
    num *= 10;
    num += c - '0';
  }
}
int main() {
  n = read_int();
  m = read_int();
  for (int i = 0; i < n; i++) {
    int a;
    a = read_int();
    v.push_back(a);
  }
  memset(us, -1, sizeof(us));
  memset(us2, -1, sizeof(us2));
  memset(ans, -1, sizeof(ans));
  for (int i = 0; i < m; i += 330) {
    int lef = i;
    int rig = i + 330;
    rig = min(rig, m);
    vv.clear();
    vals.clear();
    tmps.clear();
    for (int j = lef; j < rig; j++) {
      int ty;
      ty = read_int();
      if (ty == 1) {
        int p, x;
        p = read_int();
        x = read_int();
        p--;
        if (us2[p] != i) {
          us2[p] = i;
          vv.push_back(make_pair(make_pair(p, v[p]), -1));
          vals.push_back(make_pair(v[p], -1));
          tmps.insert(v[p]);
        }
        vv.push_back(make_pair(make_pair(p, x), j));
        if (tmps.count(x) == 0) {
          vals.push_back(make_pair(x, j));
          tmps.insert(x);
        }
        v[p] = -1;
        continue;
      } else {
        int l, r;
        l = read_int();
        r = read_int();
        l--;
        r--;
        query[r].push_back(make_pair(l, j));
      }
    }
    sort(vals.begin(), vals.end(), cmp2);
    sort(vv.begin(), vv.end(), cmp);
    memset(bit, 0, sizeof(bit));
    memset(pr, -1, sizeof(pr));
    for (int i = 0; i <= n; i++) {
      cc[i] = 0;
    }
    for (int i = 0; i < n; i++) {
      if (v[i] != -1) {
        cc[v[i]]++;
      }
    }
    for (int i = 0; i <= n; i++) {
      if (cc[i]) {
        ap[i].resize(cc[i]);
      }
      sz[i] = 0;
    }
    for (int i = 0; i < n; i++) {
      if (v[i] != -1) {
        int kind = v[i];
        ap[kind][sz[kind]] = i;
        sz[kind]++;
        if (pr[kind] >= 0) {
          add(pr[kind], i - pr[kind]);
        }
        pr[kind] = i;
      }
      if (query[i].size() == 0) continue;
      long long int all = sum(i);
      for (auto it : query[i]) {
        ans[it.second] = all;
        if (it.first) ans[it.second] -= sum(it.first - 1);
        int l = it.first;
        int r = i;
        for (auto it2 : vals) {
          if (it2.second > it.second) break;
          int ff = lower_bound(ap[it2.first].begin(),
                               ap[it2.first].begin() + sz[it2.first], l) -
                   ap[it2.first].begin();
          if (ff == sz[it2.first]) {
            mint[it2.first] = -1;
            maxt[it2.first] = -1;
          } else {
            mint[it2.first] = ap[it2.first][ff];
            maxt[it2.first] = pr[it2.first];
          }
        }
        for (int ii = vv.size() - 1; ii >= 0; ii--) {
          auto it2 = vv[ii];
          if (it2.second > it.second) {
            continue;
          }
          int pos = it2.first.first;
          int val = it2.first.second;
          if (pos < l) continue;
          if (pos > r) continue;
          if (us[pos] != it.second) {
            us[pos] = it.second;
          } else {
            continue;
          }
          if (mint[val] != -1) {
            ans[it.second] -= maxt[val] - mint[val];
          }
          if (mint[val] == -1) {
            mint[val] = maxt[val] = pos;
          }
          maxt[val] = max(maxt[val], pos);
          mint[val] = min(mint[val], pos);
          ans[it.second] += (long long int)(maxt[val] - mint[val]);
        }
      }
      query[i].clear();
    }
    for (auto it : vv) {
      v[it.first.first] = it.first.second;
    }
  }
  for (int i = 0; i < 100003; i++) {
    if (ans[i] == -1) {
      continue;
    }
    printf("%lld\n", ans[i]);
  }
  return 0;
}
