#include <bits/stdc++.h>
using namespace std;
int GLL(long long& x) { return scanf("%lld", &x); }
int GI(int& x) { return scanf("%d", &x); }
const int BLOCK = 1000;
const int BLOCKS = 105;
const int MAXN = BLOCK * BLOCKS;
int n;
int h;
long long t[2 * MAXN];
inline void calc(int p, int k) { t[p] = t[p << 1] + t[p << 1 | 1]; }
void up(int l, int r) {
  int k = 2;
  for (l += n, r += n - 1; l > 1; k <<= 1) {
    l >>= 1, r >>= 1;
    for (int i = r; i >= l; --i) calc(i, k);
  }
}
inline void apply(int p, long long value, int k) { t[p] = value; }
void update(int l, long long value) {
  int r = l + 1;
  int l0 = l, r0 = r, k = 1;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
    if (l & 1) apply(l++, value, k);
    if (r & 1) apply(--r, value, k);
  }
  up(l0, l0 + 1);
  up(r0 - 1, r0);
}
long long query(int l, int r) {
  long long res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res += t[l++];
    if (r & 1) res += t[--r];
  }
  return res;
}
int v[MAXN];
vector<set<int>> indices;
long long res[MAXN];
struct Query {
  int type;
  int a;
  int b;
  int i;
  int from;
};
bool cmpB(const Query& p, const Query& q) { return p.b < q.b; }
vector<vector<Query>> q1, q2;
int m;
int main() {
  GI(n);
  GI(m);
  for (int i = 1; i <= (int)(n); i++) GI(v[i]);
  q1.resize(BLOCKS);
  q2.resize(BLOCKS);
  for (int i = 0; i < (int)(m); i++) {
    int blk = i / BLOCK;
    Query q;
    GI(q.type);
    GI(q.a);
    GI(q.b);
    q.i = i;
    if (q.type == 1) {
      q1[blk].push_back(q);
    } else {
      q2[blk].push_back(q);
    }
  }
  memset(res, -1, sizeof res);
  indices.resize(MAXN);
  for (int blk = 0; blk < (int)(BLOCKS); blk++) {
    if (q1[blk].size() + q2[blk].size()) {
      int currR = 0;
      fill(indices.begin(), indices.end(), set<int>());
      sort(q2[blk].begin(), q2[blk].end(), cmpB);
      for (auto& q : q2[blk]) {
        while (currR < q.b) {
          currR++;
          memset(t, 0, sizeof t);
          if (indices[v[currR]].size()) {
            update(*indices[v[currR]].rbegin(),
                   currR - *indices[v[currR]].rbegin());
          }
          indices[v[currR]].insert(currR);
        }
        long long& r = res[q.i];
        r = query(q.a, q.b + 1);
        int j = 0;
        while (j < q1[blk].size() && q1[blk][j].i < q.i) {
          auto& p = q1[blk][j];
          if (p.a >= q.a && p.a <= q.b) {
            p.from = v[p.a];
            auto it = indices[p.from].find(p.a);
            auto invalid = indices[p.from].end();
            auto nit = it;
            nit++;
            if (nit != invalid && *nit > q.b) {
              nit = invalid;
            }
            auto pit = it;
            if (pit == indices[p.from].begin()) {
              pit = invalid;
            } else {
              pit--;
              if (*pit < q.a) pit = invalid;
            }
            if (pit == invalid && nit != invalid) {
              r -= *nit - p.a;
            } else if (pit != invalid && nit == invalid) {
              r -= p.a - *pit;
            }
            indices[p.from].erase(it);
            indices[p.b].insert(p.a);
            it = indices[p.b].find(p.a);
            nit = it;
            nit++;
            if (indices[p.b].size() > 1 && it == indices[p.b].begin()) {
              if (*nit <= q.b) {
                r += *nit - *it;
              }
            } else if (indices[p.b].size() > 1 && nit == indices[p.b].end()) {
              it--;
              nit--;
              if (*it >= q.a) {
                r += *nit - *it;
              }
            }
          }
          j++;
        }
        j--;
        while (j >= 0) {
          auto& p = q1[blk][j];
          if (p.a >= q.a && p.a <= q.b) {
            indices[p.b].erase(p.a);
            indices[p.from].insert(p.a);
          }
          j--;
        }
      }
    }
  }
  for (int i = 0; i < (int)(MAXN); i++) {
    if (res[i] != -1) printf("%lld\n", res[i]);
  }
  return 0;
}
