#include <bits/stdc++.h>
using namespace std;
struct cww {
  cww() {
    if (0) {
      ios::sync_with_stdio(false);
      cin.tie(0);
    }
  }
} star;
template <typename T>
inline bool chmin(T &l, T r) {
  bool a = l > r;
  if (a) l = r;
  return a;
}
template <typename T>
inline bool chmax(T &l, T r) {
  bool a = l < r;
  if (a) l = r;
  return a;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &it : v) is >> it;
  return is;
}
namespace RBST {
unsigned yy = 1145141919;
inline unsigned xorshift() {
  yy = yy ^ (yy << 13);
  yy = yy ^ (yy >> 17);
  return yy = yy ^ (yy << 5);
}
constexpr int MASK = 65535;
inline int randInt() { return (int)(xorshift() & MASK); }
const int RBST_SIZE = 2123456;
struct node {
  int val, lb, ub;
  long long latte, sum;
  int sz;
  node *lc, *rc;
  node *p;
};
typedef pair<node *, node *> pn;
inline int size(node *v) { return !v ? 0 : v->sz; }
inline node *update(node *v) {
  if (!v) return v;
  v->sz = 1 + size(v->lc) + size(v->rc);
  v->ub = !(v->rc) ? v->val : v->rc->ub;
  v->lb = !(v->lc) ? v->val : v->lc->lb;
  v->sum = v->latte;
  v->sum += !(v->lc) ? 0 : v->lc->sum;
  v->sum += !(v->rc) ? 0 : v->rc->sum;
  if (v->rc != NULL) v->rc->p = v;
  if (v->lc != NULL) v->lc->p = v;
  v->p = NULL;
  return v;
}
namespace pool {
node mem[RBST_SIZE], *que[RBST_SIZE];
int bg = 0;
struct RB {
  RB() {
    for (int i = (0); i < (RBST_SIZE); i++) que[i] = &mem[i];
  }
} ST;
void push(node *m) { que[--bg] = m; }
node *get(node val) {
  node *ret = que[bg++];
  *ret = val;
  return ret;
}
node *get(int v, long long val) {
  return get(node{v, v, v, val, val, 1, NULL, NULL, NULL});
}
}  // namespace pool
inline int lr(long long a, long long b) {
  return randInt() * (a + b) < a * MASK;
}
node *merge(node *l, node *r) {
  if (!l || !r) return !l ? update(r) : update(l);
  node *ret;
  if (lr(l->sz, r->sz)) {
    l->rc = merge(l->rc, r);
    ret = update(l);
  } else {
    r->lc = merge(l, r->lc);
    ret = update(r);
  }
  return ret;
}
pn split(node *v, int key) {
  if (!v) return pn(NULL, NULL);
  if (v->val < key) {
    pn s = split(v->rc, key);
    v->rc = s.first;
    return pn(update(v), s.second);
  } else {
    pn s = split(v->lc, key);
    v->lc = s.second;
    return pn(s.first, update(v));
  }
}
node *lower_bound(node *v, int key) {
  if (!v) return v;
  if (v->val < key) {
    return lower_bound(v->rc, key);
  } else {
    node *u = lower_bound(v->lc, key);
    return !u ? v : u;
  }
}
node *min(node *v) { return !v->lc ? v : min(v->lc); }
node *max(node *v) { return !v->rc ? v : max(v->rc); }
node *nxt(node *v, node *p = NULL) {
  if (!p) {
    if (v->rc != NULL) return min(v->rc);
  } else {
    if (v->lc == p) return v;
  }
  return !v->p ? NULL : nxt(v->p, v);
}
node *prv(node *v, node *p = NULL) {
  if (!p) {
    if (v->lc != p) return max(v->lc);
  } else {
    if (v->rc == p) return v;
  }
  return !v->p ? NULL : prv(v->p, v);
}
struct RBST {
  node *root;
  RBST() { root = NULL; }
  bool isempty() { return !root; }
  int size() {
    if (isempty())
      return 0;
    else
      root->sz;
  }
  bool exist(int key) {
    node *v = lower_bound(root, key);
    return v && v->val == key;
  }
  bool erase(int key) {
    auto l_mr = split(root, key);
    auto m_r = split(l_mr.second, key + 1);
    root = merge(l_mr.first, m_r.second);
    if (!m_r.first)
      return false;
    else {
      pool::push(m_r.first);
      return true;
    }
  }
  bool insert(int key, long long val) {
    node *ins = pool::get(key, val);
    auto l_r = split(root, key);
    root = merge(merge(l_r.first, ins), l_r.second);
    return true;
  }
  long long get(int a, int b, node *v) {
    if (v == NULL) return 0;
    if (a <= v->lb && v->ub <= b) {
      return v->sum;
    }
    if (v->ub < a || b < v->lb) {
      return 0;
    }
    long long ret = a <= v->val && v->val <= b ? v->latte : 0;
    ret += get(a, b, v->lc);
    ret += get(a, b, v->rc);
    return ret;
  }
  long long get(int a, int b) { return get(a, b, root); }
};
}  // namespace RBST
struct node {
  RBST::RBST b;
};
long long mg(node &v, int key) { return v.b.get(-1, key); }
long long mg(long long l, long long r) { return l + r; }
namespace ST {
node mem[1][2123456];
int cnt = 0;
node *get() { return mem[cnt++]; }
}  // namespace ST
struct seg_tree {
  int size;
  node *seg;
  void init(int l, int r, int k = 0) {
    auto &v = seg[k];
    v.b = RBST::RBST();
    if (r - l == 1) {
    } else if (r - l > 1) {
      int m = (l + r) / 2;
      init(l, m, k * 2 + 1);
      init(m, r, k * 2 + 2);
    }
  }
  seg_tree(int n) {
    size = 1;
    while (size < n) size *= 2;
    seg = ST::get();
    init(0, size);
  }
  long long get(int a, int b, int k, int l, int r) {
    if (a <= l) {
      if (0)
        cout << l << r << " " << seg[k].b.size() << " " << mg(seg[k], b - 1)
             << "\n";
      return mg(seg[k], b - 1);
    }
    int m = (l + r) / 2;
    bool ll = !(m <= a);
    bool rr = !(r <= a);
    long long ret;
    if (ll && rr)
      ret = mg(get(a, b, k * 2 + 1, l, m), get(a, b, k * 2 + 2, m, r));
    else if (ll)
      ret = get(a, b, k * 2 + 1, l, m);
    else
      ret = get(a, b, k * 2 + 2, m, r);
    return ret;
  }
  long long get(int a, int b) { return get(a, b, 0, 0, size); }
  void ins(int a, int b, int k, int l, int r, long long key, long long val) {
    if (r <= a || b <= l) return;
    seg[k].b.insert(key, val);
    if (a <= l && r <= b) {
    } else {
      int m = (l + r) / 2;
      ins(a, b, k * 2 + 1, l, m, key, val);
      ins(a, b, k * 2 + 2, m, r, key, val);
    }
  }
  void ins(int a, int b, long long val) {
    node q;
    ins(a, a + 1, 0, 0, size, b - 1, val);
  }
  void del(int a, int b, int k, int l, int r, long long key) {
    if (r <= a || b <= l) return;
    seg[k].b.erase(key);
    if (a <= l && r <= b) {
    } else {
      int m = (l + r) / 2;
      del(a, b, k * 2 + 1, l, m, key);
      del(a, b, k * 2 + 2, m, r, key);
    }
  }
  void del(int a, int b) {
    node q;
    del(a, a + 1, 0, 0, size, b - 1);
  }
};
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<int> v(n);
  vector<set<int>> x(n);
  seg_tree seg(n + 10);
  for (int i = (0); i < (n); i++) {
    int a;
    scanf("%d", &a);
    a--;
    v[i] = a;
    x[a].insert(i);
  }
  for (int i = (0); i < (n); i++) {
    int prv = -1;
    for (auto &now : x[i]) {
      if (prv >= 0) {
        int len = now - prv;
        seg.ins(prv, now + 1, len);
      }
      prv = now;
    }
  }
  auto check = [&]() {
    for (int l = (1); l < (n + 1); l++)
      for (int r = (l); r < (n + 1); r++) {
        vector<set<int>> s(n);
        for (int i = (l - 1); i < (r); i++) s[v[i]].insert(i);
        long long ans = 0;
        for (int i = (0); i < (n); i++)
          if (s[i].size()) {
            ans += (*s[i].rbegin()) - (*s[i].begin());
          }
        if (ans != seg.get(l - 1, r)) {
          return false;
        }
      }
    return true;
  };
  for (int i = (0); i < (q); i++) {
    int type;
    scanf("%d", &type);
    if (type == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%lld\n", seg.get(l - 1, r));
    } else {
      int p, val;
      scanf("%d%d", &p, &val);
      p--;
      val--;
      if (v[p] == val) continue;
      {
        auto &td = x[v[p]];
        {
          auto ym = td.find(p);
          if (ym != td.begin()) {
            auto yb = ym;
            yb--;
            seg.del(*yb, (*ym) + 1);
          }
          {
            auto ye = ym;
            ye++;
            if (ye != td.end()) {
              seg.del(*ym, (*ye) + 1);
              if (ym != td.begin()) {
                auto yb = ym;
                yb--;
                seg.ins(*yb, (*ye) + 1, (*ye - (*yb)));
              }
            }
          }
        }
        td.erase(p);
      }
      v[p] = val;
      {
        auto &td = x[val];
        td.insert(p);
        {
          auto ym = td.find(p);
          if (ym != td.begin()) {
            auto yb = ym;
            yb--;
            seg.ins(*yb, (*ym) + 1, *ym - *yb);
          }
          {
            auto ye = ym;
            ye++;
            if (ye != td.end()) {
              if (ym != td.begin()) {
                auto yb = ym;
                yb--;
                seg.del(*yb, (*ye) + 1);
              }
              seg.ins(*ym, (*ye) + 1, *ye - *ym);
            }
          }
        }
      }
    }
  }
  return 0;
}
