Bessie 最近收到了一套颜料，她想给牧场尽头的一段长栅栏上色。栅栏由 $N$ 个连续的 $1$ 米长的段组成（$1\le N\le 2\cdot 10^5$）。Bessie 有 $N$ 种不同的颜色可用，她按颜色深浅递增的顺序将它们标记为 $1$ 到 $N$（$1$ 是非常浅的颜色，$N$ 是非常深的颜色）。因此，她可以用一个包含 $N$ 个整数的数组来描述每个栅栏段所需的颜色。

最初，所有栅栏段都是未上色的。Bessie 可以用单次笔触给任意连续的段涂上同一种颜色，前提是她不能在较深的颜色上涂较浅的颜色（她只能在较浅的颜色上涂较深的颜色）。

例如，一段长度为 4 的初始未上色栅栏可以按如下方式上色：

0000 -> 1110 -> 1122 -> 1332

不幸的是，Bessie 没有时间浪费在等待油漆干燥上。因此，Bessie 认为她可能需要让一些栅栏段保持未上色状态！目前，她正在考虑 $Q$ 个候选区间（$1\le Q\le 2\cdot 10^5$），每个区间由两个整数 $(a,b)$ 描述，其中 $1 \leq a \leq b \leq N$，表示要上色的区间 $a \ldots b$ 的端点索引。

对于每个候选区间，为了将区间内的每个栅栏段涂上其所需的颜色，同时让区间外的所有栅栏段保持未上色，最少需要多少次笔触？注意，Bessie 在此过程中实际上并没有进行任何涂色，因此每个候选区间的答案是相互独立的。

输入格式

第一行包含 $N$ 和 $Q$。

下一行包含一个由 $N$ 个整数组成的数组，表示每个栅栏段所需的颜色。

接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $a$ 和 $b$，表示一个待涂色的候选区间。

输出格式

对于每个候选区间，输出一行答案。

样例

样例输入 1

8 4
1 2 2 1 1 2 3 2
4 6
3 6
1 6
5 8

样例输出 1

2
3
3
3

说明

在此示例中，对应于所需图案

1 1 2 

2 1 1 2

1 2 2 1 1 2

1 2 3 2

子任务

• 测试点 1-2 满足 $N,Q\le 100$。
• 测试点 3-5 满足 $N,Q\le 5000$。
• 在测试点 6-10 中，输入数组不包含大于 $10$ 的整数。
• 测试点 11-20 满足没有额外限制。