#include <bits/stdc++.h>
using namespace std;
int multitest = 0;
struct query {
  int type;
  int l, r;
  int val = 0;
  query(int t, int ll, int rr, int val) {
    type = t;
    l = ll;
    r = rr;
    this->val = val;
  }
};
struct Bit {
  vector<int> node[100006];
  vector<long long> f[100006];
  int find(int i, int j) {
    return (lower_bound(node[i].begin(), node[i].end(), j) - node[i].begin());
  }
  void fakeU(int i, int j) {
    while (i < 100006) {
      node[i].push_back(j);
      i |= (i + 1);
    }
  }
  void fakeG(int i, int j) {
    while (i >= 0) {
      node[i].push_back(j);
      i &= (i + 1);
      i--;
    }
  }
  void topo() {
    for (int i = 0; i < 100006; i++) {
      sort(node[i].begin(), node[i].end());
      node[i].resize(unique(node[i].begin(), node[i].end()) - node[i].begin());
      f[i].assign(node[i].size() + 2, 0);
    }
  }
  void Up(int i, int j, int val) {
    while (i < 100006) {
      int ptr = find(i, j);
      while (ptr >= 0) {
        f[i][ptr] += val;
        ptr &= (ptr + 1);
        ptr--;
      }
      i |= (i + 1);
    }
  }
  long long Get(int i, int j) {
    long long res = 0;
    while (i >= 0) {
      int ptr = find(i, j);
      while (ptr < f[i].size()) {
        res += f[i][ptr];
        ptr |= (ptr + 1);
      }
      i &= (i + 1);
      i--;
    }
    return res;
  }
  vector<long long> solve(vector<query> _query) {
    for (auto q : _query) {
      if (q.type == 1)
        fakeU(q.l, q.r);
      else
        fakeG(q.r, q.l), fakeG(q.l - 1, q.l);
    }
    vector<long long> ans;
    topo();
    for (auto q : _query) {
      if (q.type == 1) {
        Up(q.l, q.r, q.val);
      } else
        ans.push_back(Get(q.r, q.l) - Get(q.l - 1, q.l));
    }
    return ans;
  }
};
Bit Work;
set<int> S[100006];
vector<int> A;
vector<query> Q;
int n, q;
void change(int p, int val) {
  vector<int> c(0, 0);
  auto it = S[A[p]].find(p);
  if (it != S[A[p]].begin()) {
    c.push_back(*(--it));
    it++;
  }
  c.push_back(p);
  it++;
  if (it != S[A[p]].end()) {
    c.push_back(*it);
  }
  if (c.size() == 1) return;
  if (c.size() == 2) {
    Q.push_back(query(1, c[1], c[0], (c[1] - c[0]) * val));
  } else {
    Q.push_back(query(1, c[1], c[0], (c[1] - c[0]) * val));
    Q.push_back(query(1, c[2], c[1], (c[2] - c[1]) * val));
    Q.push_back(query(1, c[2], c[0], (c[2] - c[0]) * -1 * val));
  }
}
void solve() {
  scanf("%d", &n);
  scanf("%d", &q);
  A.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
    S[A[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    auto it = S[A[i]].find(i);
    if (it != S[A[i]].begin()) {
      --it;
      Q.push_back(query(1, i, *it, i - *it));
    }
  }
  while (q--) {
    int t, p, s;
    scanf("%d", &t);
    scanf("%d", &p);
    scanf("%d", &s);
    if (t == 1) {
      change(p, -1);
      S[A[p]].erase(p);
      A[p] = s;
      S[s].insert(p);
      change(p, 1);
    } else {
      Q.push_back(query(2, p, s, 0));
    }
  }
  vector<long long> ans = Work.solve(Q);
  for (auto z : ans) cout << z << '\n';
}
void input() {}
int main() {
  if (multitest) {
    int t;
    cin >> t;
    while (t--) {
      input();
      solve();
    }
  } else {
    input();
    solve();
  }
}
