#include <bits/stdc++.h>
using namespace std;
int const N = 1e5 + 13;
int const INF = 1e9 + 13;
int n, m;
set<int> p[N];
int l[N], r[N];
int pos[N], x[N];
int tsz;
int a[N];
int type[N];
vector<int> t[N * 4], tright[N * 4];
vector<long long> F[N * 4];
vector<int> qid;
vector<pair<int, int>> qpos[N];
vector<int> lposes;
bool cmpl(int i, int j) { return l[i] < l[j]; }
void merge(vector<int> &v, vector<int> &l, vector<int> &r) {
  int lp = 0;
  int rp = 0;
  int ln = l.size();
  int rn = r.size();
  while (lp < ln || rp < rn) {
    if (rp == rn || (lp < ln && ::r[l[lp]] < ::r[r[rp]])) {
      v.push_back(l[lp++]);
    } else {
      v.push_back(r[rp++]);
    }
  }
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v].push_back(qid[tl]);
    F[v].assign(1, 0LL);
    for (int i = 0; i < t[v].size(); ++i) {
      qpos[t[v][i]].push_back(make_pair(v, i));
    }
    tright[v].push_back(r[qid[tl]]);
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2 + 1, tl, tm);
    build(v * 2 + 2, tm + 1, tr);
    merge(t[v], t[v * 2 + 1], t[v * 2 + 2]);
    for (int i = 0; i < t[v].size(); ++i) {
      qpos[t[v][i]].push_back(make_pair(v, i));
      tright[v].push_back(r[t[v][i]]);
    }
    F[v].assign(t[v].size(), 0LL);
  }
}
void updF(vector<long long> &F, int x, int v) {
  int n = F.size();
  while (x < n) {
    F[x] += v;
    x |= (x + 1);
  }
}
long long getF(vector<long long> &F, int x) {
  long long res = 0;
  while (x >= 0) {
    res += F[x];
    x = (x & (x + 1)) - 1;
  }
  return res;
}
void upd(vector<long long> &F, int l, int r, int val) {
  if (l > r) return;
  updF(F, l, val);
  updF(F, r + 1, -val);
}
int getLeft(vector<int> &v, int val) {
  int l = -1;
  int r = v.size();
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (v[m] >= val)
      r = m;
    else
      l = m;
  }
  return r;
}
int getRight(vector<int> &v, int val) {
  int l = -1;
  int r = v.size();
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (v[m] <= val)
      l = m;
    else
      r = m;
  }
  return l;
}
void upd(int v, int tl, int tr, int ll, int lr, int rl, int rr, int val) {
  if (tl > lr || ll > tr) return;
  if (ll <= tl && tr <= lr) {
    int left = getLeft(tright[v], rl);
    int right = getRight(tright[v], rr);
    upd(F[v], left, right, val);
    return;
  }
  int tm = (tl + tr) / 2;
  upd(v * 2 + 1, tl, tm, ll, lr, rl, rr, val);
  upd(v * 2 + 2, tm + 1, tr, ll, lr, rl, rr, val);
}
long long answer(int id) {
  long long res = 0;
  for (int i = 0; i < qpos[id].size(); ++i) {
    res += getF(F[qpos[id][i].first], qpos[id][i].second);
  }
  return res;
}
void push(int pos, int val) {
  set<int>::iterator bef, aft;
  bef = p[val].lower_bound(pos);
  aft = p[val].upper_bound(pos);
  if (bef != p[val].begin()) {
    --bef;
    int lp = (*bef);
    int dist = pos - lp;
    lp = getRight(lposes, lp);
    int rp = (aft == p[val].end() ? INF : (*aft) - 1);
    upd(0, 0, tsz - 1, 0, lp, pos, rp, dist);
  }
  bef = p[val].lower_bound(pos);
  aft = p[val].upper_bound(pos);
  if (aft != p[val].end()) {
    int lp;
    if (bef != p[val].begin()) {
      --bef;
      lp = (*bef) + 1;
    } else {
      lp = 0;
    }
    lp = getLeft(lposes, lp);
    int rp = getRight(lposes, pos);
    int rpp = (*aft);
    int dist = rpp - pos;
    upd(0, 0, tsz - 1, lp, rp, rpp, INF, dist);
  }
  p[val].insert(pos);
}
void pop(int pos, int val) {
  p[val].erase(pos);
  set<int>::iterator bef, aft;
  bef = p[val].lower_bound(pos);
  aft = p[val].upper_bound(pos);
  if (bef != p[val].begin()) {
    --bef;
    int lp = (*bef);
    int dist = pos - lp;
    lp = getRight(lposes, lp);
    int rp = (aft == p[val].end() ? INF : (*aft) - 1);
    upd(0, 0, tsz - 1, 0, lp, pos, rp, -dist);
  }
  bef = p[val].lower_bound(pos);
  aft = p[val].upper_bound(pos);
  if (aft != p[val].end()) {
    int lp;
    if (bef != p[val].begin()) {
      --bef;
      lp = (*bef) + 1;
    } else {
      lp = 0;
    }
    lp = getLeft(lposes, lp);
    int rp = getRight(lposes, pos);
    int rpp = (*aft);
    int dist = rpp - pos;
    upd(0, 0, tsz - 1, lp, rp, rpp, INF, -dist);
  }
}
void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < m; ++i) {
    cin >> type[i];
    if (type[i] == 1) {
      cin >> pos[i] >> x[i];
      --pos[i];
    } else {
      cin >> l[i] >> r[i];
      --l[i];
      --r[i];
      qid.push_back(i);
    }
  }
  tsz = qid.size();
  if (tsz == 0) return;
  sort(qid.begin(), qid.end(), cmpl);
  for (int i = 0; i < qid.size(); ++i) lposes.push_back(l[qid[i]]);
  build(0, 0, tsz - 1);
  for (int i = 0; i < n; ++i) push(i, a[i]);
  for (int i = 0; i < m; ++i) {
    if (type[i] == 1) {
      pop(pos[i], a[pos[i]]);
      a[pos[i]] = x[i];
      push(pos[i], a[pos[i]]);
    } else {
      long long ans = answer(i);
      cout << ans << endl;
    }
  }
}
int main() {
  solve();
  return 0;
}
