#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 8;
int n, q, tot, num, a[N];
long long ans[N];
struct node {
  int type, x, y, id;
  bool operator<(const node &b) const {
    return x < b.x || x == b.x && type < b.type;
  }
  void print() { cout << type << " " << x << " " << y << " " << id << endl; }
} Q[N], tmp[N];
set<int> S[N];
struct BIT {
  long long a[N];
  int len;
  void init(int l) {
    len = l;
    for (int i = 0; i < len; ++i) a[i] = 0;
  }
  void insert(int x, int y) {
    for (int i = x; i < len; i += i & (-i)) a[i] += y;
  }
  long long query(int x) {
    long long res = 0;
    for (int i = x; i > 0; i -= i & (-i)) res += a[i];
    return res;
  }
  void clear(int x) {
    for (int i = x; i < len; i += i & (-i))
      if (a[i] != 0)
        a[i] = 0;
      else
        break;
  }
} T;
void cdq(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  cdq(l, mid);
  cdq(mid + 1, r);
  int i = l, j = mid + 1;
  for (int k = l; k <= r; ++k)
    if (j > r || i <= mid && Q[i] < Q[j]) {
      tmp[k] = Q[i++];
      if (tmp[k].type == 1) T.insert(n - tmp[k].y + 1, tmp[k].id);
    } else {
      tmp[k] = Q[j++];
      if (tmp[k].type == 2) ans[tmp[k].id] += T.query(n - tmp[k].y + 1);
    }
  for (int k = l; k <= r; ++k) {
    Q[k] = tmp[k];
    T.clear(n - tmp[k].y + 1);
  }
}
void update(int pos, int y) {
  if (a[pos] == y) return;
  auto it = S[a[pos]].find(pos);
  auto it1 = it;
  it1--;
  auto it2 = it;
  it2++;
  Q[++tot] = (node){1, *it, *it1, *it1 - *it};
  Q[++tot] = (node){1, *it2, *it, *it - *it2};
  Q[++tot] = (node){1, *it2, *it1, *it2 - *it1};
  S[a[pos]].erase(pos);
  a[pos] = y;
  S[a[pos]].insert(pos);
  it = S[a[pos]].find(pos);
  it1 = it;
  it1--;
  it2 = it;
  it2++;
  Q[++tot] = (node){1, *it, *it1, *it - *it1};
  Q[++tot] = (node){1, *it2, *it, *it2 - *it};
  Q[++tot] = (node){1, *it2, *it1, *it1 - *it2};
}
void init() {
  cin >> n >> q;
  tot = 0;
  for (int i = 1; i <= n; ++i) S[i].insert(0), S[i].insert(n + 1);
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    a[i] = x;
    S[x].insert(i);
    auto it = S[x].find(i);
    it--;
    Q[++tot] = (node){1, i, *it, i - (*it)};
  }
  num = 0;
  for (int i = 1; i <= q; ++i) {
    int type, x, y;
    cin >> type >> x >> y;
    if (type == 2)
      Q[++tot] = (node){2, y, x, ++num};
    else
      update(x, y);
  }
}
void solve() {
  T.init(n + 10);
  cdq(1, tot);
  for (int i = 1; i <= num; ++i) cout << ans[i] << endl;
}
int main() {
  cin.sync_with_stdio(0);
  init();
  solve();
}
