#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9, SIZ = 1.593e7 + 7;
const int SCN = 1.4e5;
int n, m;
namespace ScapegoatTree {
const double alpha = 0.75;
struct ScapegoatNode {
  unsigned v : 19;
  unsigned tot : 2;
  unsigned siz : 19;
  int l, r;
} t[SCN * 2] = {0};
int root[N];
int temp[SCN];
int TempCnt, NodeCnt;
bool Balance(int x) {
  return t[t[x].l].siz < t[x].siz * alpha && t[t[x].r].siz < t[x].siz * alpha;
}
void Flatten(int x) {
  if (!x) return;
  Flatten(t[x].l);
  if (t[x].tot) temp[++TempCnt] = x;
  Flatten(t[x].r);
}
void Build(int &x, int l, int r) {
  if (l > r) return void(x = 0);
  if (l == r) {
    x = temp[l];
    t[x].l = 0;
    t[x].r = 0;
    t[x].siz = t[x].tot;
    return;
  }
  int mid = (l + r) >> 1;
  x = temp[mid];
  Build(t[x].l, l, mid - 1);
  Build(t[x].r, mid + 1, r);
  t[x].siz = t[t[x].l].siz + t[t[x].r].siz + t[x].tot;
}
void ReBuild(int &x) {
  TempCnt = 0;
  Flatten(x);
  Build(x, 1, TempCnt);
}
void Check(int &a) {
  if (!a) return;
  if (!Balance(a))
    ReBuild(a);
  else if (t[t[a].l].siz > t[t[a].r].siz)
    Check(t[a].l);
  else
    Check(t[a].r);
}
void Tree_Do_Insert(int &a, int v) {
  if (!a) {
    a = ++NodeCnt;
    t[a].v = v;
    t[a].tot = 1;
  } else if (v == t[a].v) {
    t[a].tot++;
  } else if (v < t[a].v) {
    Tree_Do_Insert(t[a].l, v);
  } else {
    Tree_Do_Insert(t[a].r, v);
  }
  t[a].siz++;
}
void Tree_Do_Erase(int a, int v) {
  if (v == t[a].v) {
    t[a].tot--;
  } else if (v < t[a].v) {
    Tree_Do_Erase(t[a].l, v);
  } else {
    Tree_Do_Erase(t[a].r, v);
  }
  t[a].siz--;
}
int GetVal(int u, int rank) {
  int a = root[u];
  if (rank <= 0) return 0;
  if (rank > t[a].siz) return n + 1;
  while (true) {
    if (t[t[a].l].siz < rank && t[t[a].l].siz + t[a].tot >= rank)
      return t[a].v;
    else if (t[t[a].l].siz >= rank)
      a = t[a].l;
    else
      rank -= t[t[a].l].siz + t[a].tot, a = t[a].r;
  }
}
int GetRank(int u, int val) {
  int a = root[u], rank = 1;
  while (a) {
    if (t[a].v >= val)
      a = t[a].l;
    else
      rank += t[t[a].l].siz + t[a].tot, a = t[a].r;
  }
  return rank;
}
int GetPrev(int u, int val) { return GetVal(u, GetRank(u, val) - 1); }
int GetNext(int u, int val) { return GetVal(u, GetRank(u, val + 1)); }
void Insert(int u, int val) {
  Tree_Do_Insert(root[u], val);
  Check(root[u]);
}
void Erase(int u, int val) {
  Tree_Do_Erase(root[u], val);
  Check(root[u]);
}
};  // namespace ScapegoatTree
namespace SegmentTree_2D {
struct interval {
  int l : 24;
  int r : 24;
  interval() : l(0), r(0) {}
  interval(int L, int R) {
    l = L;
    r = R;
  }
  inline int mid() const { return (l + r) >> 1; }
  inline interval get_L() const { return interval(l, mid()); }
  inline interval get_R() const { return interval(mid() + 1, r); }
  inline int size() const { return r - l + 1; }
  inline bool exist() const { return l <= r; }
  inline bool isInclude(int pos) const { return pos >= l && pos <= r; }
  inline bool isInclude(interval s) const { return s.l >= l && s.r <= r; }
  inline bool noUnion(interval s) const { return s.r < l || s.l > r; }
  inline bool only_point(int pos) const { return pos == l && pos == r; }
} full;
struct square {
  interval x, y;
  square() : x(), y() {}
  square(interval L, interval R) : x(L), y(R) {}
  square(int xl, int xr, int yl, int yr) : x(xl, xr), y(yl, yr) {}
  inline square get_L() const { return square(x, y.get_L()); }
  inline square get_R() const { return square(x, y.get_R()); }
  inline square get_U() const { return square(x.get_L(), y); }
  inline square get_D() const { return square(x.get_R(), y); }
  inline square get_LU() const { return square(x.get_L(), y.get_L()); }
  inline square get_RU() const { return square(x.get_L(), y.get_R()); }
  inline square get_LD() const { return square(x.get_R(), y.get_L()); }
  inline square get_RD() const { return square(x.get_R(), y.get_R()); }
  inline bool exist() const { return x.exist() && y.exist(); }
  inline bool isInclude(int X, int Y) const {
    return x.isInclude(X) && y.isInclude(Y);
  }
  inline bool isInclude(square s) const {
    return x.isInclude(s.x) && y.isInclude(s.y);
  }
  inline bool noUnion(square s) const {
    return x.noUnion(s.x) || y.noUnion(s.y);
  }
  inline bool only_point(int X, int Y) const {
    return x.only_point(X) && y.only_point(Y);
  }
};
int rt[N << 2], cnt = 0;
struct SegmentTreeNode {
  int l, r;
  long long val : 48;
} t[SIZ] = {0};
void update_(int &u, interval now, interval upd, int dif) {
  if (!now.exist() || upd.noUnion(now)) return;
  if (!u) u = ++cnt;
  if (upd.isInclude(now)) {
    t[u].val = t[u].val + dif;
    return;
  }
  update_(t[u].l, now.get_L(), upd, dif);
  update_(t[u].r, now.get_R(), upd, dif);
}
void update(int u, interval now, square upd, int dif) {
  if (!now.exist() || upd.x.noUnion(now)) return;
  if (upd.x.isInclude(now)) {
    update_(rt[u], full, upd.y, dif);
    return;
  }
  update(u << 1, now.get_L(), upd, dif);
  update(u << 1 | 1, now.get_R(), upd, dif);
}
long long query_(const int &u, interval now, int x) {
  if (!now.exist() || !now.isInclude(x) || !u) return 0;
  if (now.only_point(x)) return (long long)t[u].val;
  return query_(t[u].l, now.get_L(), x) + query_(t[u].r, now.get_R(), x) +
         (long long)t[u].val;
}
long long query(int u, interval now, int x, int y) {
  if (!now.exist() || !now.isInclude(x)) return 0;
  if (now.only_point(x)) return query_(rt[u], full, y);
  if (x <= now.mid())
    return query(u << 1, now.get_L(), x, y) + query_(rt[u], full, y);
  else
    return query(u << 1 | 1, now.get_R(), x, y) + query_(rt[u], full, y);
}
};  // namespace SegmentTree_2D
namespace against_cpp11 {
int a[N];
signed main() {
  scanf("%d%d", &n, &m);
  SegmentTree_2D::full = SegmentTree_2D::interval(0, n + 1);
  for (int i = 1, l, r; i <= n; i++) {
    scanf("%d", a + i);
    ScapegoatTree::Insert(a[i], i);
    l = ScapegoatTree::GetPrev(a[i], i);
    r = ScapegoatTree::GetNext(a[i], i);
    SegmentTree_2D::update(1, SegmentTree_2D::full,
                           SegmentTree_2D::square(0, l, i, r - 1), i - l);
    SegmentTree_2D::update(1, SegmentTree_2D::full,
                           SegmentTree_2D::square(l + 1, i, r, n + 1), r - i);
  }
  for (int i = 1, opt, x, y, l, r; i <= m; i++) {
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1) {
      ScapegoatTree::Erase(a[x], x);
      l = ScapegoatTree::GetPrev(a[x], x);
      r = ScapegoatTree::GetNext(a[x], x);
      SegmentTree_2D::update(1, SegmentTree_2D::full,
                             SegmentTree_2D::square(0, l, x, r - 1), l - x);
      SegmentTree_2D::update(1, SegmentTree_2D::full,
                             SegmentTree_2D::square(l + 1, x, r, n + 1), x - r);
      a[x] = y;
      ScapegoatTree::Insert(a[x], x);
      l = ScapegoatTree::GetPrev(a[x], x);
      r = ScapegoatTree::GetNext(a[x], x);
      SegmentTree_2D::update(1, SegmentTree_2D::full,
                             SegmentTree_2D::square(0, l, x, r - 1), x - l);
      SegmentTree_2D::update(1, SegmentTree_2D::full,
                             SegmentTree_2D::square(l + 1, x, r, n + 1), r - x);
    } else {
      printf("%lld\n", SegmentTree_2D::query(1, SegmentTree_2D::full, x, y));
    }
  }
  return 0;
}
}  // namespace against_cpp11
signed main() { return against_cpp11::main(); }
