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>
using namespace std;
using ll = long long;
template <typename S, typename T>
void xmin(S& a, T const& b) {
  if (b < a) a = b;
}
template <typename S, typename T>
void xmax(S& a, T const& b) {
  if (b > a) a = b;
}
class avlTree {
 public:
  struct node {
    static node sent;
    node *l, *r;
    int x, height;
    ll y, suby;
    int subSize;
    node(int _x, ll _y)
        : l(&sent), r(&sent), x(_x), height(1), y(_y), suby(y), subSize(1) {}
    int h() {
      if (this == &sent) return 0;
      return height;
    }
    int s() {
      if (this == &sent) return 0;
      return subSize;
    }
    node* recalc() {
      subSize = 1 + l->s() + r->s();
      height = 1 + max(l->h(), r->h());
      suby = y + (l ? l->suby : 0) + (r ? r->suby : 0);
      return this;
    }
  } * root;
  static node* sent;
  avlTree() : root(sent) {}

 private:
  static node* balance(node* a, node* l, node* r) {
    if (l->h() > r->h() + 1) {
      if (l->l->h() >= l->r->h()) {
        a->l = l->r;
        a->r = r;
        a->recalc();
        l->r = a;
        return l->recalc();
      }
      a->l = l->r->r;
      a->r = r;
      a->recalc();
      node* ret = l->r;
      l->r = l->r->l;
      l->recalc();
      ret->r = a;
      ret->l = l;
      return ret->recalc();
    } else if (r->h() > l->h() + 1) {
      if (r->r->h() >= r->l->h()) {
        a->r = r->l;
        a->l = l;
        a->recalc();
        r->l = a;
        return r->recalc();
      }
      a->l = l;
      a->r = r->l->l;
      a->recalc();
      node* ret = r->l;
      r->l = r->l->r;
      r->recalc();
      ret->r = r;
      ret->l = a;
      return ret->recalc();
    }
    a->l = l;
    a->r = r;
    return a->recalc();
  }
  static node* flat_merge(node* a, node* l, node* r) {
    return balance(a, l, r);
  }
  static node* insert(node* a, node* val) {
    if (a == sent) return val;
    if (val->x == a->x) {
      a->y += val->y;
      delete val;
      return a->recalc();
    }
    if (val->x < a->x) {
      return balance(a, insert(a->l, val), a->r);
    } else {
      return balance(a, a->l, insert(a->r, val));
    }
  }
  static node* push_front(node* a, node* val) {
    if (a == sent) return val;
    return balance(a, push_front(a->l, val), a->r);
  }
  static node* push_back(node* a, node* val) {
    if (a == sent) return val;
    return balance(a, a->l, push_back(a->r, val));
  }
  static node* merge(node* a, node* l, node* r) {
    if (l == sent) return push_front(r, a);
    if (r == sent) return push_back(l, a);
    if (l->h() > r->h() + 1) {
      return balance(l, l->l, merge(a, l->r, r));
    }
    if (r->h() > l->h() + 1) {
      return balance(r, merge(a, l, r->l), r->r);
    }
    a->l = l;
    a->r = r;
    return a->recalc();
  }
  static node* front(node* a) {
    while (a->l) a = a->l;
    return a;
  }
  static node* back(node* a) {
    while (a->r) a = a->r;
    return a;
  }
  static node* pop_front(node* a) {
    if (a->l) return balance(a, pop_front(a->l), a->r);
    return a->r;
  }
  static node* pop_back(node* a) {
    if (a->r) return balance(a, a->l, pop_back(a->r));
    return a->l;
  }
  static node* merge(node* a, node* b) {
    if (a == sent) return b;
    if (b == sent) return a;
    node* m = front(b);
    return merge(m, a, pop_front(b));
  }
  static node* flat_merge(node* a, node* b) {
    if (a == sent) return b;
    if (b == sent) return a;
    node* m = front(b);
    return balance(m, a, pop_front(b));
  }
  static pair<node*, node*> split(node* a, int pos) {
    if (a == sent) {
      assert(pos == 0);
      return make_pair(sent, sent);
    }
    if (pos <= a->l->s()) {
      pair<node*, node*> L = split(a->l, pos);
      return make_pair(L.first, merge(a, L.second, a->r));
    }
    pair<node*, node*> R = split(a->r, pos - 1 - a->l->s());
    return make_pair(merge(a, a->l, R.first), R.second);
  }
  static pair<node*, node*> splitval(node* a, int val) {
    if (a == sent) {
      return make_pair(sent, sent);
    }
    if (val < a->x) {
      pair<node*, node*> L = splitval(a->l, val);
      return make_pair(L.first, merge(a, L.second, a->r));
    }
    pair<node*, node*> R = splitval(a->r, val);
    return make_pair(merge(a, a->l, R.first), R.second);
  }
  static node* erase(node* a, int pos) {
    if (pos == a->l->s()) {
      node* ret = flat_merge(a->l, a->r);
      delete a;
      return ret;
    }
    if (pos < a->l->s()) return balance(a, erase(a->l, pos), a->r);
    return balance(a, a->l, erase(a->r, pos - 1 - a->l->s()));
  }
  static node* eraseval(node* a, int val) {
    if (val == a->x) {
      node* ret = merge(a->l, a->r);
      return ret;
    }
    if (val < a->x) return balance(a, eraseval(a->l, val), a->r);
    return balance(a, a->l, eraseval(a->r, val));
  }
  static void destroy(node* a) {
    if (a == sent) return;
    destroy(a->l);
    destroy(a->r);
    delete a;
  }

 public:
  static void check_balance(node* cur) {
    if (cur->l) check_balance(cur->l);
    if (cur->r) check_balance(cur->r);
    int lH = cur->l->h();
    int rH = cur->r->h();
    assert(lH <= rH + 1 && rH <= lH + 1);
  }
  static void traverse(ostream& o, node* cur) {
    if (cur == sent) return;
    o << " ( ";
    if (cur->l) traverse(o, cur->l);
    o << cur->x << "[" << cur->height << "," << cur->subSize << "]";
    if (cur->r) traverse(o, cur->r);
    o << ")";
  }
  void insert(int x, ll y) { root = insert(root, new node(x, y)); }
  void erase(int pos) { root = erase(root, pos); }
  void eraseval(int val) { root = eraseval(root, val); }
  int lower_count(int x) {
    int ret = 0;
    for (node* cur = root; cur != sent;) {
      if (x < cur->x)
        cur = cur->l;
      else {
        ret += 1 + cur->l->s();
        cur = cur->r;
      }
    }
    return ret;
  }
  void destroy() { destroy(root); }
  void update(int y, ll val) { insert(y, val); }
  ll q(int y) {
    ll ans = 0;
    for (node* cur = root; cur != sent;) {
      if (y < cur->x)
        cur = cur->l;
      else {
        ans += cur->y + (cur->l ? cur->l->suby : 0);
        cur = cur->r;
      }
    }
    return ans;
  }
  ll query(int y1, int y2) { return q(y2 - 1) - q(y1 - 1); }
};
avlTree::node avlTree::node::sent(0, 0);
avlTree::node* avlTree::sent = &node::sent;
;
struct tree2d {
  int n;
  vector<avlTree> data;
  tree2d(int _n) : n(_n + 2), data(n) {}
  ll q(int x, int y1, int y2) {
    ll ans = 0;
    for (; x; x -= (x & -x)) {
      ans += data[x].query(y1, y2);
    }
    return ans;
  }
  ll query(int x1, int x2, int y1, int y2) {
    return q(x2, y1, y2) - q(x1, y1, y2);
  }
  void u(int x, int y, ll val) {
    ++x;
    for (; x < n; x += (x & -x)) {
      data[x].update(y, val);
    }
  }
  void update(int x, int y, ll val) { u(x, y, val); }
};
signed gen(int n) {
  int m = n;
  ofstream o("gen.txt");
  o << n << "  " << m << "\n";
  mt19937 rng(21536);
  auto getrand = [&](int r) {
    return uniform_int_distribution<int>(0, r - 1)(rng);
  };
  for (int i = 0; i < n; ++i) {
    o << getrand(1 + n / 10) << " ";
  }
  o << endl;
  for (int i = 0; i < m; ++i) {
    o << (i % 2) + 1 << " " << 1 + getrand(n) << " " << 1 + getrand(n) << "\n";
  }
  o << endl;
  o.close();
  return 0;
}
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  tree2d tr(n);
  vector<set<int> > bu(n + 1);
  vector<int> a(n);
  for (auto& e : a) {
    cin >> e;
  }
  for (int i = 0; i < n; ++i) {
    if (!bu[a[i]].empty()) {
      int l = *bu[a[i]].rbegin();
      tr.update(l, i, i - l);
    }
    bu[a[i]].insert(i);
  }
  for (int i = 0; i < m; ++i) {
    int t, b, c;
    cin >> t >> b >> c;
    if (t == 1) {
      --b;
      auto it = bu[a[b]].find(b);
      auto up = [&](ll s) {
        auto it2 = next(it);
        if (it2 != bu[a[b]].end()) {
          int l = b;
          int r = *it2;
          tr.update(l, r, s * (r - l));
        }
        if (it != bu[a[b]].begin()) {
          auto it3 = prev(it);
          int l = *it3;
          int r = b;
          tr.update(l, r, s * (r - l));
          if (it2 != bu[a[b]].end()) {
            l = *it3;
            r = *it2;
            tr.update(l, r, -s * (r - l));
          }
        }
      };
      up(-1);
      bu[a[b]].erase(b);
      a[b] = c;
      bu[a[b]].insert(b);
      it = bu[a[b]].find(b);
      up(1);
    } else {
      --b;
      --c;
      ll ans = tr.query(b, n + 1, 0, c + 1);
      cout << ans << "\n";
    }
  }
  return 0;
}
