#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100005];
int tmp[100005];
set<int> ori[100005];
set<int> s[100005];
unordered_set<int> exc;
int t[200005];
unsigned int qr(int l, int r) {
  unsigned int res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res += t[l++];
    if (r & 1) res += t[--r];
  }
  return res;
}
void upd(int pos, int val) {
  for (t[pos += n] = val; pos > 1; pos >>= 1) t[pos >> 1] = t[pos] + t[pos ^ 1];
  return;
}
void calc() {
  exc.clear();
  for (int i = 1; i <= n; i++) ori[i] = s[i];
  for (int i = 1; i <= n; i++) tmp[i] = a[i];
  for (int i = 0; i < 200005; i++) t[i] = 0;
  return;
}
int ti[100005], xi[100005], yi[100005];
unsigned int res[100005];
vector<int> cur[100005];
vector<int> cur2[100005];
int last[100005];
void getans() {
  for (int i = 1; i <= n; i++) last[i] = 0;
  for (int i = 1; i <= n; i++) {
    if (last[tmp[i]]) upd(last[tmp[i]], 0);
    last[tmp[i]] = i;
    upd(i, i);
    for (int id : cur[i]) {
      res[id] += qr(xi[id], yi[id] + 1);
    }
    cur[i].clear();
  }
  for (int i = 0; i < 200005; i++) t[i] = 0;
  for (int i = 1; i <= n; i++) last[i] = 0;
  for (int i = n; i >= 1; i--) {
    if (last[tmp[i]]) upd(last[tmp[i]], 0);
    last[tmp[i]] = i;
    upd(i, i);
    for (int id : cur2[i]) {
      res[id] -= qr(xi[id], yi[id] + 1);
    }
    cur2[i].clear();
  }
  return;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) a[i] = i % 50000 + 1, s[a[i]].insert(i);
  int re_num = 250;
  auto it = s[0].begin();
  for (int qr = 0; qr < m; qr++) {
    if (qr % re_num == 0) {
      getans();
      calc();
    }
    ti[qr] = 2, xi[qr] = 1, yi[qr] = n;
    if (ti[qr] == 1) {
      exc.insert(a[xi[qr]]);
      s[a[xi[qr]]].erase(xi[qr]);
      a[xi[qr]] = yi[qr];
      s[a[xi[qr]]].insert(xi[qr]);
      exc.insert(a[xi[qr]]);
    } else {
      for (int x : exc) {
        it = s[x].lower_bound(xi[qr]);
        if (it != s[x].end() && (*it) <= yi[qr]) {
          res[qr] -= *it;
          it = s[x].upper_bound(yi[qr]);
          it--;
          res[qr] += *it;
        }
        it = ori[x].lower_bound(xi[qr]);
        if (it != ori[x].end() && (*it) <= yi[qr]) {
          res[qr] += *it;
          it = ori[x].upper_bound(yi[qr]);
          it--;
          res[qr] -= *it;
        }
      }
      cur[yi[qr]].push_back(qr);
      cur2[xi[qr]].push_back(qr);
    }
  }
  getans();
  long long x = (1LL << 32);
  for (int i = 0; i < m; i++)
    if (ti[i] == 2) {
      if (res[i] < 0) res[i] += x;
      printf("%u\n", res[i]);
    }
  return 0;
}
