I won't feel lonely, nor will I be sorrowful... not before everything is buried.

A string of n beads is left as the message of leaving. The beads are numbered from 1 to n from left to right, each having a shape numbered by integers between 1 and n inclusive. Some beads may have the same shapes.

The memory of a shape x in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape x appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.

From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

Input

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 100 000) — the number of beads in the string, and the total number of changes and queries, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n) — the initial shapes of beads 1, 2, ..., n, respectively.

The following m lines each describes either a change in the beads or a query of subsegment. A line has one of the following formats: 

  * 1 p x (1 ≤ p ≤ n, 1 ≤ x ≤ n), meaning that the shape of the p-th bead is changed into x; 
  * 2 l r (1 ≤ l ≤ r ≤ n), denoting a query of memory of the subsegment from l to r, inclusive. 

Output

For each query, print one line with an integer — the memory of the recalled subsegment.

Examples

Input

7 6
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6
2 5 7


Output

5
0
7
1


Input

7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7


Output

0
0

Note

The initial string of beads has shapes (1, 2, 3, 1, 3, 2, 1).

Consider the changes and queries in their order: 

  1. 2 3 7: the memory of the subsegment [3, 7] is (7 - 4) + (6 - 6) + (5 - 3) = 5; 
  2. 2 1 3: the memory of the subsegment [1, 3] is (1 - 1) + (2 - 2) + (3 - 3) = 0; 
  3. 1 7 2: the shape of the 7-th bead changes into 2. Beads now have shapes (1, 2, 3, 1, 3, 2, 2) respectively; 
  4. 1 3 2: the shape of the 3-rd bead changes into 2. Beads now have shapes (1, 2, 2, 1, 3, 2, 2) respectively; 
  5. 2 1 6: the memory of the subsegment [1, 6] is (4 - 1) + (6 - 2) + (5 - 5) = 7; 
  6. 2 5 7: the memory of the subsegment [5, 7] is (7 - 6) + (5 - 5) = 1. 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const double PI = acos(-1);
const int _ML = 500;
const char _inpf[] = "";
const char _outf[] = "";
template <typename T, typename U>
inline ostream &operator<<(ostream &_out, const pair<T, U> &_p) {
  _out << _p.first << ' ' << _p.second;
  return _out;
}
template <typename T, typename U>
inline istream &operator>>(istream &_in, pair<T, U> &_p) {
  _in >> _p.first >> _p.second;
  return _in;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const vector<T> &_v) {
  if (_v.empty()) {
    return _out;
  }
  _out << _v.front();
  for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline istream &operator>>(istream &_in, vector<T> &_v) {
  for (auto &_i : _v) {
    _in >> _i;
  }
  return _in;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const set<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const multiset<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const unordered_set<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T>
inline ostream &operator<<(ostream &_out, const unordered_multiset<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &_out, const map<T, U> &_m) {
  if (_m.empty()) {
    return _out;
  }
  _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')';
  for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) {
    _out << ", (" << _it->first << ": " << _it->second << ')';
  }
  return _out;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &_out, const unordered_map<T, U> &_m) {
  if (_m.empty()) {
    return _out;
  }
  _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')';
  for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) {
    _out << ", (" << _it->first << ": " << _it->second << ')';
  }
  return _out;
}
const int N = 100 * 1000 + 228;
pair<int, int> val[N];
set<int> num[N];
struct node {
  long long sum;
  pair<int, int> first;
  int l, r;
  int second;
};
node *t[4 * N];
node mem[N * 18 * 4];
int mp = 1;
inline node *new_t(pair<int, int> p) {
  mem[mp] = {p.second, p, 0, 0, rand()};
  return mem + mp++;
}
inline long long get_sum(node *v) {
  if (v == mem) {
    return 0;
  }
  return v->sum;
}
inline void recalc_t(node *v) {
  v->sum = v->first.second + get_sum(mem + v->l) + get_sum(mem + v->r);
}
inline long long sum_t(node *v, int k) {
  long long sum = 0;
  while (v != mem) {
    if (v->first.first >= k) {
      sum += v->first.second + get_sum(mem + v->r);
      v = mem + v->l;
    } else {
      v = mem + v->r;
    }
  }
  return sum;
}
pair<node *, node *> split_t(node *v, pair<int, int> k) {
  if (v == mem) {
    return {mem, mem};
  }
  if (v->first < k) {
    auto p = split_t(mem + v->r, k);
    v->r = p.first - mem;
    recalc_t(v);
    return {v, p.second};
  } else {
    auto p = split_t(mem + v->l, k);
    v->l = p.second - mem;
    recalc_t(v);
    return {p.first, v};
  }
}
node *merge_t(node *a, node *b) {
  if (a == mem) {
    return b;
  }
  if (b == mem) {
    return a;
  }
  if (a->second > b->second) {
    a->r = merge_t(mem + a->r, b) - mem;
    recalc_t(a);
    return a;
  } else {
    b->l = merge_t(a, mem + b->l) - mem;
    recalc_t(b);
    return b;
  }
}
node *ins_t(node *v, node *t) {
  auto p = split_t(v, t->first);
  return merge_t(p.first, merge_t(t, p.second));
}
node *ers_t(node *v, pair<int, int> k) {
  auto p = split_t(v, k);
  k.second++;
  auto q = split_t(p.second, k);
  return merge_t(p.first, q.second);
}
long long get_t(int v, int l, int r, int L, int R) {
  if (R <= l || r <= L) {
    return 0;
  }
  if (L <= l && r <= R) {
    return sum_t(t[v], L);
  }
  return get_t(v << 1, l, (l + r) >> 1, L, R) +
         get_t(v << 1 | 1, (l + r) >> 1, r, L, R);
}
void upd_t_add(int v, int l, int r, int L, pair<int, int> P) {
  if (L < l || r <= L) {
    return;
  }
  t[v] = ins_t(t[v], new_t(P));
  if (r - l > 1) {
    upd_t_add(v << 1, l, (l + r) >> 1, L, P);
    upd_t_add(v << 1 | 1, (l + r) >> 1, r, L, P);
  }
}
void upd_t_rem(int v, int l, int r, int L, pair<int, int> P) {
  if (L < l || r <= L) {
    return;
  }
  t[v] = ers_t(t[v], P);
  if (r - l > 1) {
    upd_t_rem(v << 1, l, (l + r) >> 1, L, P);
    upd_t_rem(v << 1 | 1, (l + r) >> 1, r, L, P);
  }
}
int a[N];
inline void mainFunction(void) {
  fill(t, t + 4 * N, (node *)mem);
  int n, m;
  cin >> n >> m;
  map<int, int> prv;
  for (int i = 1; i <= n; ++i) {
    int first;
    cin >> first;
    a[i] = first;
    val[i] = {prv[first], i - prv[first]};
    prv[first] = i;
    num[first].insert(i);
    upd_t_add(1, 1, n + 1, i, val[i]);
  }
  for (int i = 0; i < m; ++i) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 1) {
      int old = a[l];
      int now = r;
      a[l] = r;
      auto pos = num[old].find(l);
      auto nxt = pos;
      upd_t_rem(1, 1, n + 1, l, val[l]);
      ++nxt;
      if (nxt != num[old].end()) {
        upd_t_rem(1, 1, n + 1, *nxt, val[*nxt]);
        val[*nxt] = {val[l].first, *nxt - val[l].first};
        upd_t_add(1, 1, n + 1, *nxt, val[*nxt]);
      }
      num[old].erase(pos);
      num[now].insert(l);
      pos = num[now].find(l);
      nxt = pos;
      ++nxt;
      if (nxt != num[now].end()) {
        val[l] = {val[*nxt].first, l - val[*nxt].first};
        upd_t_rem(1, 1, n + 1, *nxt, val[*nxt]);
        val[*nxt] = {l, *nxt - l};
        upd_t_add(1, 1, n + 1, *nxt, val[*nxt]);
      } else {
        if (pos == num[now].begin()) {
          val[l] = {0, l};
        } else {
          --pos;
          val[l] = {*pos, l - *pos};
        }
      }
      upd_t_add(1, 1, n + 1, l, val[l]);
    } else {
      cout << get_t(1, 1, n + 1, l, r + 1) << '\n';
    }
  }
}
int main() {
  if (_inpf[0] != '\0') assert(freopen(_inpf, "r", stdin) != nullptr);
  if (_outf[0] != '\0') assert(freopen(_outf, "w", stdout) != nullptr);
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << setprecision(20);
  mainFunction();
}
