#include <bits/stdc++.h>
using namespace std;
int n, m, q[100005][3], z[100005], ii[100005][2], ta, tb, tc;
set<int> s[100005];
set<int>::iterator it, itt;
vector<int> x[100005][2], y[100005][2];
vector<pair<int, pair<int, int> > > v[18][100005][2];
vector<vector<pair<long long, int> > > w[18][100005][2];
long long ans;
void f1(int a, int b, int c, int d) {
  if (((1 << (c)) * (d)) == a && ((1 << (c)) * (d + 1)) == b) {
    tc = 0;
    for (int i = w[c][d][0].size() - 1; i >= 0 && tc < w[c][d][0][i].size();
         i--) {
      if (w[c][d][0][i][tc].second < ta) {
        if (w[c][d][0][i][tc].first) printf("- %d\n", w[c][d][0][i][tc].first);
        ans -= w[c][d][0][i][tc].first;
        tc++;
      }
      tc *= 2;
    }
    tc = 1;
    for (int i = w[c][d][1].size() - 1; i >= 0 && tc; i--) {
      tc = min(tc, (int)w[c][d][1][i].size());
      if (w[c][d][1][i][tc - 1].second >= tb) {
        if (w[c][d][1][i][tc - 1].first)
          printf("+ %d\n", w[c][d][1][i][tc - 1].first);
        ans += w[c][d][1][i][tc - 1].first;
        tc--;
      }
      tc *= 2;
    }
    return;
  }
  c--, d = d * 2 + 1;
  if (b <= ((1 << (c)) * (d)))
    f1(a, b, c, d - 1);
  else if (a >= ((1 << (c)) * (d)))
    f1(a, b, c, d);
  else
    f1(a, ((1 << (c)) * (d)), c, d - 1), f1(((1 << (c)) * (d)), b, c, d);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", z + i);
    s[z[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    s[i].insert(-1);
    s[i].insert(n);
    for (it = s[i].begin(); it != s[i].end(); it++)
      if (*it != -1 && *it != n) {
        itt = it;
        itt--;
        x[*it][0].push_back(*itt);
        itt = it;
        itt++;
        x[*it][1].push_back(*itt);
      }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 3; j++) scanf("%d", q[i] + j);
    q[i][1]--;
    if (q[i][0] == 1 && z[q[i][1]] != q[i][2]) {
      it = s[z[q[i][1]]].find(q[i][1]);
      itt = it;
      itt--;
      ta = *itt;
      itt = it;
      itt++;
      tb = *itt;
      if (ta != -1) {
        y[i][1].push_back(ta);
        x[ta][1].push_back(tb);
      }
      if (tb != n) {
        y[i][0].push_back(tb);
        x[tb][0].push_back(ta);
      }
      s[z[q[i][1]]].erase(it);
      it = s[z[q[i][1]] = q[i][2]].insert(q[i][1]).first;
      itt = it;
      itt--;
      ta = *itt;
      itt = it;
      itt++;
      tb = *itt;
      if (ta != -1) {
        y[i][1].push_back(ta);
        x[ta][1].push_back(q[i][1]);
      }
      if (tb != n) {
        y[i][0].push_back(tb);
        x[tb][0].push_back(q[i][1]);
      }
      y[i][0].push_back(q[i][1]);
      x[q[i][1]][0].push_back(ta);
      y[i][1].push_back(q[i][1]);
      x[q[i][1]][1].push_back(tb);
    }
  }
  for (int i = 0; i < n; i++) {
    ta = i;
    for (int j = 0; j < 18; j++) {
      for (int k = 0; k < 2; k++)
        for (int l = 0; l < x[i][k].size(); l++)
          v[j][ta][k].push_back(make_pair(x[i][k][l], make_pair(i, l)));
      ta /= 2;
    }
  }
  for (int i = 0; i < 18; i++)
    for (int j = 0; ((1 << (i)) * (j)) < n; j++)
      for (int k = 0; k < 2; k++) {
        sort(v[i][j][k].begin(), v[i][j][k].end());
        w[i][j][k].push_back(vector<pair<long long, int> >());
        for (int l = 0; l < v[i][j][k].size(); l++)
          w[i][j][k].back().push_back(
              make_pair(v[i][j][k][l].second.second
                            ? 0LL
                            : (long long)v[i][j][k][l].second.first,
                        v[i][j][k][l].first));
        while (w[i][j][k].back().size() > 1) {
          ta = w[i][j][k].size() - 1;
          tb = w[i][j][k].back().size();
          w[i][j][k].push_back(vector<pair<long long, int> >());
          for (int l = 0; l < tb; l += 2) {
            if (l + 1 < tb) {
              if (k)
                tc = w[i][j][k][ta][l].second;
              else
                tc = w[i][j][k][ta][l + 1].second;
              w[i][j][k].back().push_back(make_pair(
                  w[i][j][k][ta][l].first + w[i][j][k][ta][l + 1].first, tc));
            } else
              w[i][j][k].back().push_back(w[i][j][k][ta][l]);
          }
        }
      }
  for (int i = 0; i < m; i++)
    if (q[i][0] == 1) {
      for (int j = 0; j < 2; j++)
        if (!y[i][j].empty())
          for (int p = 0; p < y[i][j].size(); p++) {
            ta = y[i][j][p];
            int l = ta;
            for (int k = 0; k < 18; k++) {
              tb = lower_bound(v[k][l][j].begin(), v[k][l][j].end(),
                               make_pair(x[ta][j][ii[ta][j]],
                                         make_pair(ta, ii[ta][j]))) -
                   v[k][l][j].begin();
              for (int r = 0; r < w[k][l][j].size(); r++) {
                w[k][l][j][r][tb].first -= ta;
                tb /= 2;
              }
              l /= 2;
            }
            ii[ta][j]++;
            l = ta;
            for (int k = 0; k < 18; k++) {
              tb = lower_bound(v[k][l][j].begin(), v[k][l][j].end(),
                               make_pair(x[ta][j][ii[ta][j]],
                                         make_pair(ta, ii[ta][j]))) -
                   v[k][l][j].begin();
              for (int r = 0; r < w[k][l][j].size(); r++) {
                w[k][l][j][r][tb].first += ta;
                tb /= 2;
              }
              l /= 2;
            }
          }
    } else {
      ans = 0;
      f1(ta = q[i][1], tb = q[i][2], 17, 0);
      printf("%lld\n", ans);
    }
  return 0;
}
