### 问题描述 小齐最近收到了一套油漆工具，她想要给她牧场尽头的长篱笆涂上颜色。这个篱笆由 $N$ 个相邻的 $1$ 米长段组成。小齐有 $N$ 种不同的颜色可用，她用字母 $1$ 到 $N$ 表示它们，颜色的深浅按照字母的增加顺序（$1$ 为非常浅的颜色，$N$ 为非常深的颜色）。因此，她可以用一个包含 $N$ 个整数的数组描述她想要给每个篱笆段涂的颜色。 最初，所有篱笆段都未着色。小齐可以用一次刷涂任何一个连续的段范围，只要她不在较深的颜色上涂覆较浅的颜色（她只能在较浅的颜色上涂覆较深的颜色）。 给定 $Q$ 个候选范围，每个由两个整数 $a$ 和 $b$ 描述，其中 $1 \leq a \leq b \leq N$ 表示可能要涂色的段的端点索引。 对于每个候选范围，求在将范围内的每个篱笆段涂上其期望颜色的同时留下所有范围外的篱笆段未着色所需的最小刷涂次数。注意，小齐在这个过程中并没有真正进行任何涂色，因此对于每个候选范围的答案是独立的。 ### 输入格式 第一行包含两个整数 $N$ 和 $Q$。 第二行包含一个包含 $N$ 个整数的数组，表示每个篱笆段的期望颜色。 接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $a$ 和 $b$，表示可能的候选范围。 ### 输出格式 对于每个候选范围，输出一个新行表示答案。 ### 样例输入 ``` 8 4 1 2 2 1 1 2 3 2 4 6 3 6 1 6 5 8 ``` ### 样例输出 ``` 2 3 3 3 ``` ### 评测数据规模 $1 \leq N, Q \leq 5000$。