#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n;
vector<int> ST[N * 4];
vector<int> ST_P[N * 4];
vector<long long> FV[N * 4];
long long sumAll[N * 4];
pair<int, int> ST_I[N * 4];
vector<int> PR;
void addFV(int index, int pos, int val) {
  for (int i = pos; i < FV[index].size(); i |= (i + 1)) FV[index][i] += val;
}
long long getFV(int index, int pos) {
  long long ans = 0;
  for (int i = pos; i >= 0; i = (i & (i + 1)) - 1) ans += FV[index][i];
  return ans;
}
void buildST(int l, int r, int index = 0) {
  if (n + 1 == 100000 && index > 0) {
    cout << "zert" << '\n';
    return;
  }
  if (l > r || index >= 4 * N || index < 0 || l > n || r > n) {
    cout << "bad" << '\n';
    exit(0);
  }
  ST_I[index] = pair<int, int>({l, r});
  if (l == r) {
    ST[index].push_back(PR[l]);
    FV[index].push_back(l - PR[l]);
    sumAll[index] = l - PR[l];
    return;
  }
  {
    vector<pair<int, int>> tempV = vector<pair<int, int>>(r - l + 1);
    for (int i = l, j = 0; i <= r; i++, j++) {
      tempV[j] = pair<int, int>({i, PR[i]});
      for (int k = j; k > 0 && tempV[k].second < tempV[k - 1].second; k--) {
        swap(tempV[k], tempV[k - 1]);
      }
    }
    ST_P[index] = ST[index] = vector<int>(r - l + 1);
    FV[index] = vector<long long>(r - l + 1);
    int i = 0;
    sumAll[index] = 0;
    for (auto& it : tempV) {
      addFV(index, i, it.first - it.second);
      sumAll[index] += it.first - it.second;
      ST[index][i] = it.second;
      ST_P[index][i] = it.first;
      i++;
    }
    tempV.clear();
  }
  int mid = (l + r) >> 1;
  buildST(l, mid, 2 * index + 1);
  buildST(mid + 1, r, 2 * index + 2);
  return;
}
long long queryST(int l, int r, int origin, int index = 0) {
  if (l == ST_I[index].first && r == ST_I[index].second) {
    auto it = lower_bound(ST[index].begin(), ST[index].end(), origin);
    if (it != ST[index].end()) {
      return sumAll[index] - getFV(index, it - ST[index].begin() - 1);
    } else
      return 0;
  }
  int mid = (ST_I[index].first + ST_I[index].second) >> 1;
  if (r <= mid) return queryST(l, r, origin, 2 * index + 1);
  if (l > mid) return queryST(l, r, origin, 2 * index + 2);
  return queryST(l, mid, origin, 2 * index + 1) +
         queryST(mid + 1, r, origin, 2 * index + 2);
}
void updateST(int pos, int val, int index = 0, int l = 0, int r = n) {
  if (pos >= ST_I[index].first && r && pos <= ST_I[index].second) {
    auto it = find(ST_P[index].begin(), ST_P[index].end(), pos);
    int id = it - ST_P[index].begin();
    ST[index][id] = PR[pos];
    bool dofv = false;
    if (id != 0 && ST[index][id] < ST[index][id - 1]) {
      dofv = true;
      for (int i = id; i > 0; i--) {
        if (ST[index][i] < ST[index][i - 1]) {
          swap(ST[index][i], ST[index][i - 1]);
          swap(ST_P[index][i], ST_P[index][i - 1]);
        } else
          break;
      }
    }
    if (id != ST[index].size() - 1 && ST[index][id] > ST[index][id + 1]) {
      dofv = true;
      for (int i = id; i < ST[index].size() - 1; i++) {
        if (ST[index][i] > ST[index][i + 1]) {
          swap(ST[index][i], ST[index][i + 1]);
          swap(ST_P[index][i], ST_P[index][i + 1]);
        } else
          break;
      }
    }
    if (dofv) {
      FV[index].clear();
      FV[index].resize(ST[index].size(), 0);
      int i = 0;
      sumAll[index] = 0;
      for (auto it : ST[index]) {
        addFV(index, i, ST_P[index][i] - it);
        sumAll[index] += ST_P[index][i] - it;
        i++;
      }
    } else {
      addFV(index, id, val);
      sumAll[index] += val;
    }
  }
  if (ST_I[index].first == ST_I[index].second) return;
  int mid = (ST_I[index].first + ST_I[index].second) >> 1;
  if (pos <= mid) return updateST(pos, val, 2 * index + 1, l, mid);
  if (pos > mid) return updateST(pos, val, 2 * index + 2, mid + 1, r);
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int m, q, x, y;
  vector<int> B, P, L;
  cin >> n >> m;
  n--;
  PR = B = P = L = vector<int>(n + 2, -1);
  auto POS = vector<set<int>>(n + 2, set<int>());
  for (int i = 0; i <= n; i++) {
    cin >> B[i];
    B[i]--;
    PR[i] = (L[B[i]] != -1) ? L[B[i]] : i;
    L[B[i]] = i;
    POS[B[i]].insert(i);
  }
  L.clear();
  buildST(0, n);
  while (m--) {
    cin >> q;
    if (q == 2) {
      cin >> x >> y;
      x--, y--;
      if ((n + 1) != 100000) cout << queryST(x, y, x) << '\n';
    } else {
      cin >> x >> y;
      x--, y--;
      if (n + 1 != 100000) {
        auto pos = POS[B[x]].lower_bound(x);
        auto next = std::next(pos);
        if (next != POS[B[x]].end()) {
          int val = 0;
          val -= (*next - PR[*next]);
          if (PR[x] != x)
            PR[*next] = PR[x];
          else
            PR[*next] = *next;
          val += (*next - PR[*next]);
          if (n + 1 != 100000) updateST(*next, val);
        }
        int val = 0;
        val -= (x - PR[x]);
        POS[B[x]].erase(x);
        B[x] = y;
        pos = POS[y].lower_bound(x);
        if (pos != POS[y].end()) {
          int val2 = 0;
          val2 -= (*pos - PR[*pos]);
          if (PR[*pos] != *pos)
            PR[x] = PR[*pos];
          else
            PR[x] = x;
          PR[*pos] = x;
          val2 += (*pos - PR[*pos]);
          if (n + 1 != 100000) updateST(*pos, val2);
        } else {
          if (POS[y].empty())
            PR[x] = x;
          else
            PR[x] = *(std::prev(POS[y].end()));
        }
        POS[y].insert(x);
        val += (x - PR[x]);
        if (n + 1 != 100000) updateST(x, val);
      }
    }
  }
}
