#include <bits/stdc++.h>
using namespace std;
template <int n>
using AI = array<int, n>;
typedef AI<2> AII;
typedef AI<3> AI3;
typedef AI<4> AI4;
const double eps = 1e-9;
const int oo = 0x3F3F3F3F;
const long long ooLL = 0x3F3F3F3F3F3F3F3FLL;
const int MOD = 1000000007;
template <typename T>
T sqr(T x) {
  return x * x;
}
const double PI = acos(-1.);
long long Round(double x) { return x < 0 ? x - .5 : x + .5; }
int main() {
  void run();
  run();
  return 0;
}
const int N = 1 << 17;
map<int, set<int>> h;
AI4 re[N * 6];
int res;
vector<pair<int, long long>> tt[N];
int n, m, a[N];
long long rs[N];
void addv(int x, int y) {
  for (; x < N; x = x | (x + 1)) tt[x].emplace_back(y, 0);
}
void addcv(int x, int y) {
  for (; x >= 0; x = (x & (x + 1)) - 1) tt[x].emplace_back(y, 0);
}
void tmod(int x, int y0, int p) {
  for (; x < N; x = x | (x + 1)) {
    int y = lower_bound((tt[x]).begin(), (tt[x]).end(), make_pair(y0, -1LL)) -
            tt[x].begin();
    for (; y < tt[x].size(); y = y | (y + 1)) {
      tt[x][y].second += p;
    }
  }
}
long long tc(int x, int y0) {
  long long c = 0;
  for (; x >= 0; x = (x & (x + 1)) - 1) {
    int y = lower_bound((tt[x]).begin(), (tt[x]).end(), make_pair(y0, -1LL)) -
            tt[x].begin();
    for (; y >= 0; y = (y & (y + 1)) - 1) {
      c += tt[x][y].second;
    }
  }
  return c;
}
void qmod(int x, int y, int v, int s) {
  x = n - 1 - x;
  re[res++] = {1, x, y, v * s};
  if (s > 0) addv(x, y);
}
void qc(int x, int y, int i) {
  x = n - 1 - x;
  --y;
  re[res++] = {2, x, y, i};
  addcv(x, y);
}
void mod(int p, int x, int s) {
  auto it = s > 0 ? h[x].insert(p).first : h[x].find(p);
  int l = -1, r = -1;
  auto itp = it;
  if (itp != h[x].begin()) l = *--itp;
  auto itn = it;
  ++itn;
  if (itn != h[x].end()) r = *itn;
  if (l != -1) qmod(l, p, p - l, s);
  if (r != -1) qmod(p, r, r - p, s);
  if (l != -1 && r != -1) qmod(l, r, r - l, -s);
  if (s < 0) h[x].erase(p);
}
void run() {
  scanf("%d %d", &n, &m);
  for (int i = (0), __i(n); i < __i; ++i) {
    scanf("%d", a + i);
    mod(i, a[i], 1);
  }
  for (int i = (0), __i(m); i < __i; ++i) {
    int t, l, r;
    scanf("%d %d %d", &t, &l, &r);
    --l;
    if (t == 1) {
      mod(l, a[l], -1);
      a[l] = r;
      mod(l, a[l], 1);
    } else {
      qc(l, r, i);
    }
  }
  memset(rs, -1, sizeof(rs));
  for (int i = (0), __i(N); i < __i; ++i) sort((tt[i]).begin(), (tt[i]).end());
  for (int i = (0), __i(res); i < __i; ++i) {
    int t = re[i][0], l = re[i][1], r = re[i][2], p = re[i][3];
    if (t == 1) {
      tmod(l, r, p);
    } else {
      rs[p] = tc(l, r);
    }
  }
  for (int i = (0), __i(m); i < __i; ++i)
    if (rs[i] != -1) printf("%lld\n", rs[i]);
}
