#include <bits/stdc++.h>
int num[100001], n, m, kk, m1, p[100001], sta[321], sto[321], q[100001], opt, l,
    r, a[100001];
long long g1[52][100001], g2[52][100001], ans[51][51];
long long ask(int x, int y) {
  long long ss = 0, hh;
  if (num[x] == num[y]) {
    for (long long j = x; j <= y; j++) {
      if (q[a[j]] == 0) {
        q[a[j]] = j;
        p[a[j]] = j;
      }
      hh = p[a[j]];
      ss = ss - hh;
      p[a[j]] = j;
      ss = ss + j;
    }
    for (long long j = x; j <= y; j++) {
      q[a[j]] = 0;
      p[a[j]] = n + 1;
    }
    return (ss);
  }
  int aa = num[x], bb = num[y];
  ss = ans[num[x] + 1][num[y] - 1];
  for (long long i = y; i >= sta[bb]; i--)
    if (g2[bb - 1][a[i]] < i) {
      q[a[i]] = g2[bb - 1][a[i]];
      g2[bb - 1][a[i]] = i;
      if (i > g1[aa + 1][a[i]]) {
        if (q[a[i]] > g1[aa + 1][a[i]]) {
          hh = q[a[i]] - g1[aa + 1][a[i]];
          ss = ss - hh;
        }
        hh = i - g1[aa + 1][a[i]];
        ss = ss + hh;
      }
    }
  for (long long i = x; i <= sto[aa]; i++)
    if (g1[aa + 1][a[i]] > i) {
      p[a[i]] = g1[aa + 1][a[i]];
      g1[aa + 1][a[i]] = i;
      if (i < g2[bb - 1][a[i]]) {
        if (p[a[i]] < g2[bb - 1][a[i]]) {
          hh = g2[bb - 1][a[i]] - p[a[i]];
          ss = ss - hh;
        }
        hh = g2[bb - 1][a[i]] - i;
        ss = ss + hh;
      }
    }
  for (int i = x; i <= sto[aa]; i++)
    if (g1[aa + 1][a[i]] == i) {
      g1[aa + 1][a[i]] = p[a[i]];
      p[a[i]] = n + 1;
    }
  for (int i = y; i >= sta[bb]; i--)
    if (g2[bb - 1][a[i]] == i) {
      g2[bb - 1][a[i]] = q[a[i]];
      q[a[i]] = 0;
    }
  return (ss);
}
void gai(long long x, long long y) {
  int aa = num[x];
  if (g1[aa][a[x]] == x) {
    for (int i = x + 1; i <= sto[aa]; i++)
      if (a[i] == a[x]) {
        g1[aa][a[x]] = i;
        break;
      }
    if (g1[aa][a[x]] == x) g1[aa][a[x]] = g1[aa + 1][a[x]];
    for (int i = aa; i <= m1; i++)
      if (num[g1[aa][a[x]]] <= i)
        ans[aa][i] = ans[aa][i] + x - g1[aa][a[x]];
      else if (x <= i)
        ans[aa][i] = ans[aa][i] + x - g2[i][a[x]];
    int bb = aa;
    aa--;
    while (aa != 0) {
      if (g1[aa][a[x]] < x) break;
      g1[aa][a[x]] = g1[bb][a[x]];
      for (int i = aa; i <= m1; i++)
        if (num[g1[aa][a[x]]] <= i)
          ans[aa][i] = ans[aa][i] + x - g1[aa][a[x]];
        else if (x <= i)
          ans[aa][i] = ans[aa][i] + x - g2[i][a[x]];
      aa--;
    }
  }
  aa = num[x];
  if (g2[aa][a[x]] == x) {
    for (int i = x - 1; i >= sta[aa]; i--)
      if (a[i] == a[x]) {
        g2[aa][a[x]] = i;
        break;
      }
    if (g2[aa][a[x]] == x) g2[aa][a[x]] = g2[aa - 1][a[x]];
    for (int i = aa; i >= 1; i--)
      if (num[g1[i][a[x]]] <= aa) {
        if (num[g2[aa][a[x]]] >= i)
          ans[i][aa] = ans[i][aa] + x - g1[aa][a[x]];
        else if (x <= i)
          ans[i][aa] = ans[i][aa] + x - g2[i][a[x]];
      }
    int bb = aa;
    aa++;
    while (aa != m1 + 1) {
      if (g2[aa][a[x]] > x) break;
      g2[aa][a[x]] = g2[bb][a[x]];
      for (int i = aa; i >= 1; i--)
        if (num[g1[i][a[x]]] <= aa) {
          if (num[g2[aa][a[x]]] >= i)
            ans[i][aa] = ans[i][aa] + x - g1[aa][a[x]];
          else if (x <= i)
            ans[i][aa] = ans[i][aa] + x - g2[i][a[x]];
        }
      aa++;
    }
  }
  a[x] = y;
  aa = num[x];
  if (g2[aa][a[x]] < x) {
    long long prex = g2[aa][a[x]];
    g2[aa][a[x]] = x;
    for (int i = aa; i >= 1; i--)
      if (num[g1[i][a[x]]] <= aa) {
        if (prex >= i)
          ans[i][aa] = ans[i][aa] - prex + x;
        else
          ans[i][aa] = ans[i][aa] + x - g1[i][a[x]];
      }
    int bb = aa;
    aa++;
    while (aa != m1 + 1) {
      if (g2[aa][a[x]] > x) break;
      g2[aa][a[x]] = g2[bb][a[x]];
      for (int i = aa; i >= 1; i--)
        if (num[g1[i][a[x]]] <= aa) {
          if (prex >= i)
            ans[i][aa] = ans[i][aa] - prex + x;
          else
            ans[i][aa] = ans[i][aa] + x - g1[i][a[x]];
        }
      aa++;
    }
  }
  aa = num[x];
  if (g1[aa][a[x]] > x) {
    long long prex = g1[aa][a[x]];
    g1[aa][a[x]] = x;
    for (int i = aa; i >= 1; i--)
      if (num[g2[aa][a[x]]] >= i) {
        if (prex <= aa)
          ans[i][aa] = ans[i][aa] + prex - x;
        else if (x <= aa)
          ans[i][aa] = ans[i][aa] - x + g2[aa][a[x]];
      }
    int bb = aa;
    aa--;
    while (aa != 0) {
      if (g1[aa][a[x]] < x) break;
      g1[aa][a[x]] = g1[bb][a[x]];
      for (int i = aa; i >= 1; i--)
        if (num[g2[aa][a[x]]] >= i) {
          if (prex <= aa)
            ans[i][aa] = ans[i][aa] + prex - x;
          else if (x <= aa)
            ans[i][aa] = ans[i][aa] - x + g2[aa][a[x]];
        }
      aa--;
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  kk = 2000;
  m1 = n / kk;
  if (n % kk != 0) m1++;
  for (int i = 1; i <= n; i++) {
    num[i] = i / kk;
    sto[num[i]] = i;
  }
  num[n + 1] = n + 1;
  for (int i = 1; i <= n; i++) g1[m1 + 1][i] = n + 1;
  for (int i = 1; i <= n; i++) g2[0][i] = 0;
  for (int i = 1; i <= m1; i++) sta[i] = ((i - 1) * kk) + 1;
  for (int j = 1; j <= n; j++) p[j] = n + 1;
  for (int j = m1; j >= 1; j--) {
    for (int k = sto[j]; k >= sta[j]; k--) p[a[k]] = k;
    for (int i = 1; i <= n; i++) g1[j][i] = p[i];
  }
  for (int j = 1; j <= n; j++) p[j] = 0;
  for (int j = 1; j <= m1; j++) {
    for (int k = sta[j]; k <= sto[j]; k++) p[a[k]] = k;
    for (int i = 1; i <= n; i++) g2[j][i] = p[i];
  }
  for (int i = 1; i <= m1; i++) {
    long long ss = 0, hh;
    for (int ii = 1; ii <= n; ii++) q[ii] = 0;
    for (int j = 1; j <= n; j++) p[j] = n + 1;
    for (int k = i; k <= m1; k++) {
      for (long long j = sta[k]; j <= sto[k]; j++) {
        if (q[a[j]] == 0) {
          q[a[j]] = j;
          p[a[j]] = j;
        }
        hh = p[a[j]];
        ss = ss - hh;
        p[a[j]] = j;
        ss = ss + j;
      }
      ans[i][k] = ss;
    }
  }
  for (int i = 1; i <= n; i++) q[i] = 0;
  for (int j = 1; j <= n; j++) p[j] = n + 1;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &opt, &l, &r);
    if (opt == 2)
      printf("%I64d\n", ask(l, r));
    else
      gai(l, r);
  }
}
