#include <bits/stdc++.h>
using namespace std;
struct STNode {
  long long int val;
  STNode* lolo;
  STNode* lohi;
  STNode* hilo;
  STNode* hihi;
  STNode() : val(0), lolo(0), lohi(0), hilo(0), hihi(0) {}
  long long int n_query(long long int left1, long long int right1,
                        long long int left2, long long int right2,
                        long long int l1, long long int r1, long long int l2,
                        long long int r2) {
    if (right1 <= l1 || r1 <= left1 || right2 <= l2 || r2 <= left2) {
      return 0;
    }
    if (left1 <= l1 && r1 <= right1 && left2 <= l2 && r2 <= right2) {
      return val;
    }
    long long int m1 = (l1 + r1) / 2;
    long long int m2 = (l2 + r2) / 2;
    auto sub = [&](STNode* nd, long long int x1, long long int y1,
                   long long int x2, long long int y2) -> long long int {
      if (!nd) return 0;
      return nd->n_query(left1, right1, left2, right2, x1, y1, x2, y2);
    };
    long long int vlolo = sub(lolo, l1, m1, l2, m2);
    long long int vlohi = sub(lohi, l1, m1, m2, r2);
    long long int vhilo = sub(hilo, m1, r1, l2, m2);
    long long int vhihi = sub(hihi, m1, r1, m2, r2);
    return vlolo + vlohi + vhilo + vhihi;
  };
  void n_update(long long int x1, long long int x2, long long int v,
                long long int l1, long long int r1, long long int l2,
                long long int r2) {
    if (l1 + 1 == r1 && l2 + 1 == r2) {
      assert(l1 == x1 && l2 == x2);
      val = v;
    } else {
      long long int m1 = (l1 + r1) / 2;
      long long int m2 = (l2 + r2) / 2;
      using pt_t = STNode*;
      auto sub = [&](pt_t& nd, long long int t1, long long int s1,
                     long long int t2, long long int s2) -> void {
        if (!nd) nd = new STNode();
        nd->n_update(x1, x2, v, t1, s1, t2, s2);
      };
      if (x1 < m1 && x2 < m2) sub(lolo, l1, m1, l2, m2);
      if (x1 < m1 && x2 >= m2) sub(lohi, l1, m1, m2, r2);
      if (x1 >= m1 && x2 < m2) sub(hilo, m1, r1, l2, m2);
      if (x1 >= m1 && x2 >= m2) sub(hihi, m1, r1, m2, r2);
      auto eval = [&](pt_t nd) -> long long int { return nd ? nd->val : 0; };
      val = eval(lolo) + eval(lohi) + eval(hilo) + eval(hihi);
    }
  }
};
struct SegTree {
  long long int lbnd1;
  long long int rbnd1;
  long long int lbnd2;
  long long int rbnd2;
  STNode* top;
  long long int query(long long int left1, long long int right1,
                      long long int left2, long long int right2) {
    return top->n_query(left1, right1, left2, right2, lbnd1, rbnd1, lbnd2,
                        rbnd2);
  }
  void update(long long int x1, long long int x2, long long int v) {
    top->n_update(x1, x2, v, lbnd1, rbnd1, lbnd2, rbnd2);
  }
  SegTree(long long int lb1, long long int rb1, long long int lb2,
          long long int rb2)
      : lbnd1(lb1), rbnd1(rb1), lbnd2(lb2), rbnd2(rb2) {
    top = new STNode();
  }
};
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);
  long long int n, m;
  cin >> n >> m;
  SegTree st(1, n + 1, 1, n + 1);
  vector<long long int> A(n + 1);
  vector<set<long long int>> pos(n + 1, {0, n + 1});
  for (long long int i = 1; i <= n; i++) {
    long long int a;
    cin >> a;
    A[i] = a;
    pos[a].insert(i);
  }
  vector<long long int> prev(n + 1, -1), next(n + 1, -1), rec(n + 1, -1);
  for (long long int i = 1; i <= n; i++) {
    long long int c = A[i];
    if (rec[c] >= 0) {
      st.update(i, rec[c], i - rec[c]);
      next[rec[c]] = i;
      prev[i] = rec[c];
    }
    rec[c] = i;
  }
  for (long long int _q = 0; _q < m; _q++) {
    long long int ty;
    cin >> ty;
    if (ty == 1) {
      long long int p, x;
      cin >> p >> x;
      long long int old_x = A[p];
      if (x == old_x) continue;
      long long int opr = prev[p];
      long long int onx = next[p];
      if (opr >= 0) {
        st.update(p, opr, 0);
        if (onx >= 0) {
          st.update(onx, p, 0);
          st.update(onx, opr, onx - opr);
          prev[onx] = opr;
          next[opr] = onx;
        } else {
          next[opr] = -1;
        }
      } else {
        if (onx >= 0) {
          st.update(onx, p, 0);
          prev[onx] = -1;
        }
      }
      next[p] = prev[p] = -1;
      pos[old_x].erase(p);
      auto it1 = pos[x].lower_bound(p);
      long long int nx = *it1--;
      long long int pr = *it1;
      if (nx <= n && pr >= 1) {
        st.update(nx, pr, 0);
      }
      if (nx <= n) {
        st.update(nx, p, nx - p);
        next[p] = nx;
        prev[nx] = p;
      }
      if (pr >= 1) {
        st.update(p, pr, p - pr);
        prev[p] = pr;
        next[pr] = p;
      }
      A[p] = x;
      pos[x].insert(p);
    } else if (ty == 2) {
      long long int l, r;
      cin >> l >> r;
      long long int v = st.query(l, r + 1, l, n + 1);
      cout << v << "\n";
    }
  }
  return 0;
}
