import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Div1_431C {

	int nE;
	int[] tree1 = new int[400_000];

	int nN = 0;
	long[] cnt = new long[13_500_000];
	int[] lC = new int[13_500_000];
	int[] rC = new int[13_500_000];

	long query2(int nI, int cL, int cR, int qL) {
		if (cL == cR) {
			return cnt[nI];
		} else {
			int mid = (cL + cR) >> 1;
			int sum = 0;
			if (qL <= mid) {
				if (lC[nI] != -1) {
					sum += query2(lC[nI], cL, mid, qL);
				}
				if (rC[nI] != -1) {
					sum += cnt[rC[nI]];
				}
			} else if (rC[nI] != -1) {
				sum += query2(rC[nI], mid + 1, cR, qL);
			}
			return sum;
		}
	}

	long query1(int nI, int cL, int cR, int qL, int qR) {
		if (cR < qL || qR < cL) {
			return 0;
		}
		if (qL <= cL && cR <= qR) {
			return query2(tree1[nI], 1, nE, qL);
		}

		int mid = (cL + cR) >> 1;
		return query1(nI * 2, cL, mid, qL, qR) + query1(nI * 2 + 1, mid + 1, cR, qL, qR);
	}

	long query0(int qL, int qR) {
		return query1(1, 1, nE, qL, qR);
	}

	void upd2(int nI, int cL, int cR, int uI, int uV) {
		if (cL == cR) {
			cnt[nI] += uV;
		} else {
			int mid = (cL + cR) >> 1;
			if (uI <= mid) {
				if (lC[nI] == -1) {
					lC[nI] = nN++;
				}
				upd2(lC[nI], cL, mid, uI, uV);
			} else {
				if (rC[nI] == -1) {
					rC[nI] = nN++;
				}
				upd2(rC[nI], mid + 1, cR, uI, uV);
			}
			int sum = 0;
			if (lC[nI] != -1) {
				sum += cnt[lC[nI]];
			}
			if (rC[nI] != -1) {
				sum += cnt[rC[nI]];
			}
			cnt[nI] = sum;
		}
	}

	void upd1(int nI, int cL, int cR, int uI1, int uI2, int uV) {
		upd2(tree1[nI], 1, nE, uI2, uV);
		if (cL != cR) {
			int mid = (cL + cR) / 2;
			if (uI1 <= mid) {
				upd1(nI * 2, cL, mid, uI1, uI2, uV);
			} else {
				upd1(nI * 2 + 1, mid + 1, cR, uI1, uI2, uV);
			}
		}
	}

	void upd0(int uI1, int uI2, int uV) {
		upd1(1, 1, nE, uI1, uI2, uV);
	}

	void init(int nI, int cL, int cR) {
		tree1[nI] = nN++;
		if (cL != cR) {
			int mid = (cL + cR) >> 1;
			init(nI * 2, cL, mid);
			init(nI * 2 + 1, mid + 1, cR);
		}
	}

	void execute() throws IOException {
		Arrays.fill(lC, -1);
		Arrays.fill(rC, -1);
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter printer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer inputData = new StringTokenizer(reader.readLine());
		nE = Integer.parseInt(inputData.nextToken());
		int nQ = Integer.parseInt(inputData.nextToken());
		TreeSet<Integer>[] occur = new TreeSet[nE + 1];
		for (int i = 1; i <= nE; i++) {
			occur[i] = new TreeSet<>();
		}

		int[] shape = new int[nE + 1];
		inputData = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= nE; i++) {
			shape[i] = Integer.parseInt(inputData.nextToken());
			occur[shape[i]].add(i);
		}

		init(1, 1, nE);

		for (int i = 1; i <= nE; i++) {
			Integer prev = occur[shape[i]].lower(i);
			if (prev != null) {
				upd0(i, prev, i - prev);
			}
		}

		for (int cQ = 1; cQ <= nQ; cQ++) {
			inputData = new StringTokenizer(reader.readLine());
			if (inputData.nextToken().equals("1")) {
				int ind = Integer.parseInt(inputData.nextToken());
				int nS = Integer.parseInt(inputData.nextToken());
				int oS = shape[ind];
				Integer oP = occur[oS].lower(ind);
				Integer nP = occur[nS].lower(ind);

				Integer oA = occur[oS].higher(ind);
				Integer nA = occur[nS].higher(ind);

				if (oP != null) {
					upd0(ind, oP, -(ind - oP));
				}
				if (nP != null) {
					upd0(ind, nP, ind - nP);
				}

				if (oA != null) {
					upd0(oA, ind, -(oA - ind));
					if (oP != null) {
						upd0(oA, oP, oA - oP);
					}
				}

				if (nA != null) {
					if (nP != null) {
						upd0(nA, nP, -(nA - nP));
					}
					upd0(nA, ind, nA - ind);
				}
				shape[ind] = nS;
				occur[oS].remove(ind);
				occur[nS].add(ind);
			} else {
				printer.println(
						query0(Integer.parseInt(inputData.nextToken()), Integer.parseInt(inputData.nextToken())));
			}
		}
		printer.close();
	}

	public static void main(String[] args) throws IOException {
		new Div1_431C().execute();
	}
}
