import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.SortedSet;
import java.util.Set;
import java.util.Random;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        GoodbyeSouvenir solver = new GoodbyeSouvenir();
        solver.solve(1, in, out);
        out.close();
    }

    static class GoodbyeSouvenir {
        int n;
        FenwickTree[] fenwickTrees;
        IntList[] fenwickPositions;
        SortedSet<Integer>[] byValue;
        int[] next;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            n = in.nextInt();
            int numQueries = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt() - 1;
            }
            int[] q1 = new int[numQueries];
            int[] q2 = new int[numQueries];
            int[] q3 = new int[numQueries];
            for (int i = 0; i < numQueries; i++) {
                q1[i] = in.nextInt();
                q2[i] = in.nextInt() - 1;
                q3[i] = in.nextInt() - 1;
            }

            boolean stress = false;
            if (stress) {
                Random random = new Random(0);
                final int N = 80000;
                n = N;
                numQueries = N;
                a = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = random.nextInt(n);
                }
                q1 = new int[numQueries];
                q2 = new int[numQueries];
                q3 = new int[numQueries];
                for (int i = 0; i < numQueries; i++) {
                    q1[i] = 1 + random.nextInt(2);
                    if (q1[i] == 1) {
                        q2[i] = random.nextInt(n);
                        q3[i] = random.nextInt(n);
                    } else {
                        q3[i] = random.nextInt(n);
                        q2[i] = random.nextInt(q3[i]);
                    }
                }
            }

            byValue = new SortedSet[n];
            next = new int[n];

            int treeSize = 1;
            while (treeSize < n) {
                treeSize *= 2;
            }
            treeSize *= 2;
            fenwickTrees = new FenwickTree[treeSize];
            fenwickPositions = new IntList[treeSize];

            int[] oldA = a.clone();
            for (int step = 0; step < 2; step++) {
                if (step == 1) {
                    a = oldA.clone();
                    for (int i = 0; i < treeSize; i++) {
                        if (fenwickPositions[i] != null) {
                            fenwickPositions[i].sortUnique();
                            fenwickTrees[i] = new FenwickTree(fenwickPositions[i].size);
                        }

                    }
                }

                for (int i = 0; i < n; i++) {
                    byValue[i] = new TreeSet<>();
                }
                Arrays.fill(next, -1);
                for (int i = 0; i < n; i++) {
                    add(a, i, step);
                }

                for (int queryId = 0; queryId < numQueries; queryId++) {
                    if (q1[queryId] == 1) {
                        int pos = q2[queryId];
                        int val = q3[queryId];
                        remove(a, pos, step);
                        a[pos] = val;
                        add(a, pos, step);
                    }
                    if (q1[queryId] == 2 && step == 1) {
                        int l = q2[queryId];
                        int r = q3[queryId];
                        long ans = query(0, 0, n - 1, l, r, r);
                        out.println(ans);
                    }
                }
            }
        }

        private void add(int[] a, int i, int step) {
            SortedSet<Integer> hs = byValue[a[i]].headSet(i);
            SortedSet<Integer> ts = byValue[a[i]].tailSet(i);
            int u = hs.isEmpty() ? -1 : hs.last();
            int v = ts.isEmpty() ? -1 : ts.first();
            byValue[a[i]].add(i);
            if (u >= 0) {
                if (next[u] >= 0) {
                    modify(u, -1, step);
                }
                next[u] = i;
                modify(u, +1, step);
            }
            next[i] = v;
            modify(i, +1, step);
        }

        private void remove(int[] a, int i, int step) {
            SortedSet<Integer> hs = byValue[a[i]].headSet(i);
            int u = hs.isEmpty() ? -1 : hs.last();
            int v = next[i];
            byValue[a[i]].remove(i);
            modify(i, -1, step);
            next[i] = -1;
            if (u >= 0) {
                modify(u, -1, step);
                next[u] = v;
                modify(u, +1, step);
            }
        }

        private void modify(int pos, int sign, int step) {
            modify(0, 0, n - 1, pos, sign, step);
        }

        private void modify(int root, int l, int r, int pos, int sign, int step) {
            if (next[pos] < 0) {
                return;
            }
            if (step == 0) {
                if (fenwickPositions[root] == null) {
                    fenwickPositions[root] = new IntList();
                }
                fenwickPositions[root].add(next[pos]);
            } else {
                int i = fenwickPositions[root].binarySearch(next[pos]);
                fenwickTrees[root].add(i, sign * (next[pos] - pos));
            }
            if (l == r) {
                return;
            }
            int m = (l + r) / 2;
            if (pos <= m) {
                modify(2 * root + 1, l, m, pos, sign, step);
            } else {
                modify(2 * root + 2, m + 1, r, pos, sign, step);
            }
        }

        private long query(int root, int rl, int rr, int l, int r, int origR) {
            if (rl > r || l > rr) {
                return 0;
            }
            if (l == rl && r == rr) {
                if (fenwickPositions[root] == null) {
                    return 0;
                }
                int i = fenwickPositions[root].binarySearch(origR);
                if (i < 0) {
                    i = ~i;
                    --i;
                }
                return fenwickTrees[root].sum(i);
            }
            int rm = (rl + rr) / 2;
            long res = 0;
            res += query(2 * root + 1, rl, rm, l, Math.min(r, rm), origR);
            res += query(2 * root + 2, rm + 1, rr, Math.max(l, rm + 1), r, origR);
            return res;
        }

        class FenwickTree {
            int[] a;

            FenwickTree(int n) {
                a = new int[n];
            }

            void add(int pos, int val) {
                while (pos < a.length) {
                    a[pos] += val;
                    pos |= pos + 1;
                }
            }

            int sum(int r) {
                int res = 0;
                while (r >= 0) {
                    res += a[r];
                    r = (r & (r + 1)) - 1;
                }
                return res;
            }

        }

        class IntList {
            int[] a;
            int size;

            void add(int x) {
                if (a == null) {
                    a = new int[1];
                    size = 1;
                }
                if (size == a.length) {
                    a = Arrays.copyOf(a, 3 * size / 2 + 1);
                }
                a[size++] = x;
            }

            int binarySearch(int x) {
                return Arrays.binarySearch(a, 0, size, x);
            }

            void sortUnique() {
                Arrays.sort(a, 0, size);
                int k = 0;
                for (int i = 0; i < size; i++) {
                    if (i == 0 || a[i] != a[i - 1]) {
                        a[k++] = a[i];
                    }
                }
                size = k;
                a = Arrays.copyOf(a, k);
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

