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.HashSet;
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);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        final Node[] nodeCache = new Node[1200000];
        int cachePtr = 0;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            for (int i = 0; i < nodeCache.length; i++) {
                nodeCache[i] = new Node();
            }
            int 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 = 100000;
                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]);
                    }
                }
            }


            SortedSet<Integer>[] sets = new SortedSet[n];
            SortedSet<Integer>[] nSets = new SortedSet[n];
            for (int i = 0; i < n; i++) {
                sets[i] = new TreeSet<>();
                nSets[i] = new TreeSet<>();
            }

            for (int i = 0; i < n; i++) {
                sets[a[i]].add(i);
                nSets[a[i]].add(i);
            }

            Node[] roots = new Node[n];
            int[] prev = new int[n];
            final int BLOCKSIZE = 500;
            Set<Integer> touched = new HashSet<>();
            int prevClear = 0;
            for (int queryId = 0; queryId < numQueries; queryId++) {
                if (queryId % BLOCKSIZE == 0) {
                    for (int i = prevClear; i < queryId; i++) {
                        if (q1[i] == 1) {
                            int pos = q2[i];
                            int val = q3[i];
                            sets[a[pos]].remove(pos);
                            a[pos] = val;
                            sets[a[pos]].add(pos);
                        }
                    }
                    prevClear = queryId;
                    touched.clear();
                    buildPersistentTree(roots, a, prev);
                }
                if (q1[queryId] == 1) {
                    int pos = q2[queryId];
                    int val = q3[queryId];
                    touched.add(a[pos]);
                    nSets[a[pos]].remove(pos);
                    a[pos] = val;
                    nSets[a[pos]].add(pos);
                    touched.add(a[pos]);
                } else {
                    int l = q2[queryId];
                    int r = q3[queryId];
                    long ans = query(roots[r], l, r);
                    for (int id : touched) {
                        ans -= calcOnSegment(sets[id], l, r);
                        ans += calcOnSegment(nSets[id], l, r);
                    }
                    out.println(ans);
//                out.println(cachePtr);
                }
            }
        }

        private void buildPersistentTree(Node[] roots, int[] a, int[] prev) {
            cachePtr = 0;
            int n = a.length;
            Arrays.fill(prev, -1);
            for (int i = 0; i < n; i++) {
                if (i == 0) {
                    roots[i] = build(0, n - 1);
                } else {
                    roots[i] = copy(roots[i - 1]);
                }

                int p = prev[a[i]];
                prev[a[i]] = i;

                if (p >= 0) {
                    roots[i] = add(roots[i], p, i - p);
                }
            }
        }

        private long calcOnSegment(SortedSet<Integer> set, int l, int r) {
            SortedSet<Integer> ss = set.subSet(l, r + 1);
            if (ss.isEmpty()) {
                return 0;
            }
            return ss.last() - ss.first();
        }

        private Node build(int l, int r) {
            Node root = newNode();
            root.sl = l;
            root.sr = r;
            if (l == r) {
                return root;
            }
            int m = (l + r) / 2;
            root.l = build(l, m);
            root.r = build(m + 1, r);
            return root;
        }

        private Node add(Node root, int pos, int val) {
            if (pos < root.sl || pos > root.sr) {
                return root;
            }
            Node res = copy(root);
            if (pos == root.sl && pos == root.sr) {
                res.sum += val;
                return res;
            }
            res.l = add(root.l, pos, val);
            res.r = add(root.r, pos, val);
            res.sum = res.l.sum + res.r.sum;
            return res;
        }

        private long query(Node root, int l, int r) {
            if (l > root.sr || root.sl > r) {
                return 0;
            }
            if (l <= root.sl && r >= root.sr) {
                return root.sum;
            }
            long res = 0;
            res += query(root.l, l, r);
            res += query(root.r, l, r);
            return res;
        }

        Node newNode() {
            if (cachePtr >= nodeCache.length) {
                return new Node();
            }
            return nodeCache[cachePtr++];
        }

        Node copy(Node n) {
            Node c = newNode();
            c.l = n.l;
            c.r = n.r;
            c.sl = n.sl;
            c.sr = n.sr;
            c.sum = n.sum;
            return c;
        }

        class Node {
            Node l;
            Node r;
            int sl;
            int sr;
            long sum;

        }

    }

    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());
        }

    }
}

