#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, m, a[N], type, l, r;
pair<int, int> b[N];
set<int> q[M];
inline int myrand() { return rand() ^ (rand() << 15); }
struct item {
  item *l, *r;
  int key, prior, val;
  long long sum;
  item() {}
  item(int _key, int _val) {
    key = _key;
    val = sum = _val;
    prior = myrand();
    l = r = nullptr;
  }
};
typedef item *pitem;
pitem tl, t[N];
inline long long sum(pitem v) { return v ? v->sum : 0; }
inline void upd_cnt(pitem v) {
  if (v) {
    v->sum = sum(v->l) + v->val + sum(v->r);
  }
}
void Merge(pitem &v, pitem l, pitem r) {
  if (!l || !r) {
    v = l ? l : r;
  } else if (l->prior > r->prior) {
    Merge(l->r, l->r, r);
    v = l;
  } else {
    Merge(r->l, l, r->l);
    v = r;
  }
  upd_cnt(v);
}
void Split(pitem v, int key, pitem &l, pitem &r) {
  if (!v) {
    l = r = nullptr;
    return;
  }
  if (key < v->key) {
    Split(v->l, key, l, v->l);
    r = v;
  } else {
    Split(v->r, key, v->r, r);
    l = v;
  }
  upd_cnt(v);
}
void Erase(pitem &v, int key) {
  if (v->key == key) {
    Merge(v, v->l, v->r);
  } else {
    Erase(key < v->key ? v->l : v->r, key);
  }
  upd_cnt(v);
}
void Insert(pitem &v, int key, int val) {
  Split(v, key, v, tl);
  Merge(v, v, new item(key, val));
  Merge(v, v, tl);
}
inline void tree_add(int pos) {
  for (int i = pos; i <= n; i |= i + 1) {
    Insert(t[i], b[pos].first, b[pos].second);
  }
}
inline void tree_del(int pos) {
  for (int i = pos; i <= n; i |= i + 1) {
    Erase(t[i], b[pos].first);
  }
}
inline long long tree_get(pitem &v, int key) {
  Split(v, key - 1, v, tl);
  long long ans = sum(tl);
  Merge(v, v, tl);
  return ans;
}
inline long long Get(int pos, int val) {
  long long ans = 0;
  for (int i = pos; i >= 1; i &= i + 1, i--) {
    ans += tree_get(t[i], val);
  }
  return ans;
}
inline void Add(int pos) {
  q[a[pos]].insert(pos);
  int nxt = -1, prv = -1;
  auto it = q[a[pos]].upper_bound(pos);
  if (it != q[a[pos]].end()) {
    nxt = *it;
  }
  assert(it != q[a[pos]].begin());
  it--;
  if (it != q[a[pos]].begin()) {
    it--;
    prv = *it;
  }
  if (nxt != -1) {
    tree_del(nxt);
    b[nxt] = make_pair(pos, nxt - pos);
    tree_add(nxt);
  }
  if (prv != -1) {
    b[pos] = make_pair(prv, pos - prv);
  } else {
    b[pos] = make_pair(0, 0);
  }
  tree_add(pos);
}
inline void Erase(int pos) {
  int nxt = -1, prv = -1;
  auto it = q[a[pos]].upper_bound(pos);
  if (it != q[a[pos]].end()) {
    nxt = *it;
  }
  assert(it != q[a[pos]].begin());
  it--;
  if (it != q[a[pos]].begin()) {
    it--;
    prv = *it;
  }
  q[a[pos]].erase(pos);
  if (nxt != -1) {
    tree_del(nxt);
    if (prv != -1) {
      b[nxt] = make_pair(prv, nxt - prv);
    } else {
      b[nxt] = make_pair(0, 0);
    }
    tree_add(nxt);
  }
  tree_del(pos);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  srand(time(nullptr));
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    t[i] = nullptr;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    Add(i);
  }
  for (int i = 1; i <= m; i++) {
    cin >> type >> l >> r;
    if (type == 1) {
      Erase(l);
      a[l] = r;
      Add(l);
    } else {
      cout << Get(r, l) - Get(l - 1, l) << "\n";
    }
  }
}
