#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, SIZ = 1.61e7 + 7, NN = 1.3e5 + 5;
int n, m;
namespace ScapegoatTree {
const double alpha = 0.7;
struct ScapegoatNode {
  unsigned v : 19;
  unsigned tot : 2;
  unsigned siz : 19;
  int l, r;
} t[NN * 2] = {{0, 0, 0, 0, 0}};
int root[N];
int temp[NN];
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 SegmentTreeNode {
  int l, r;
  long long val : 40;
} t[SIZ] = {{0, 0, 0}};
int cnt = 0;
void update(int &u, int l, int r, int ml, int mr, int dif) {
  if (r < ml || l > mr) return;
  if (!u) u = ++cnt;
  if (l >= ml && r <= mr) {
    t[u].val += dif;
    return;
  }
  int mid = (l + r) >> 1;
  update(t[u].l, l, mid, ml, mr, dif);
  update(t[u].r, mid + 1, r, ml, mr, dif);
}
long long query(const int &u, int l, int r, int pos) {
  if (r < pos || l > pos || !u) return 0;
  if (l == r) return (long long)t[u].val;
  int mid = (l + r) >> 1;
  return query(t[u].l, l, mid, pos) + query(t[u].r, mid + 1, r, pos) +
         (long long)t[u].val;
}
};  // namespace SegmentTree_2D
namespace BIT {
int rt[N];
void seg_update(int x, int yl, int yr, int dif) {
  while (x <= n + 2) {
    SegmentTree_2D::update(rt[x], 0, n + 1, yl, yr, dif);
    x += (x & -x);
  }
}
void update(int xl, int xr, int yl, int yr, int dif) {
  seg_update(xl + 1, yl, yr, dif);
  seg_update(xr + 2, yl, yr, -dif);
}
long long query(int x, int y) {
  long long ans = 0;
  x++;
  while (x) {
    ans += SegmentTree_2D::query(rt[x], 0, n + 1, y);
    x -= (x & -x);
  }
  return ans;
}
}  // namespace BIT
namespace against_cpp11 {
int a[N];
signed main() {
  scanf("%d%d", &n, &m);
  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);
    BIT::update(0, l, i, r - 1, i - l);
    BIT::update(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);
      BIT::update(0, l, x, r - 1, l - x);
      BIT::update(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);
      BIT::update(0, l, x, r - 1, x - l);
      BIT::update(l + 1, x, r, n + 1, r - x);
    } else {
      printf("%lld\n", BIT::query(x, y));
    }
  }
  return 0;
}
}  // namespace against_cpp11
signed main() { return against_cpp11::main(); }
