Bessie 最近收到了一套颜料，她想要给她的牧草地一端的栅栏上色。栅栏由 N个 1 米长的小段组成（1≤N≤2⋅10$^5$）。Bessie 可以使用 N 种不同的颜色，她将这些颜色由浅到深用 1 到 N 标号（1 是很浅的颜色，N 是很深的颜色）。从而她可以用一个长为 N 的整数数组来描述她想要给栅栏的每一小段涂上的颜色。初始时，所有栅栏小段均未被上色。Bessie 一笔可以给任意连续若干小段涂上同一种颜色，只要她不会在较深的颜色之上涂上较浅的颜色（她只能用较深的颜色覆盖较浅的颜色）。

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

0000 -> 1110 -> 1122 -> 1332

不幸的是，Bessie 没有足够的时间等待颜料变干。所以，Bessie 认为她可能需要放弃为栅栏上某些小段上色！现在，她正在考虑 Q 个候选的区间（1≤Q≤2⋅10$^5$），每个区间用满足 1≤a≤b≤N 的两个整数 (a,b) 表示，为需要上色的小段 a…b 的两端点位置。

对于每个候选区间，将所有区间内的栅栏小段都涂上所希望的颜色，并且区间外的栅栏小段均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选区间的回答是独立的。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 N 和 Q。下一行包含一个长为 N 的整数数组，表示每个栅栏小段所希望的颜色。

以下 Q 行，每行包含两个空格分隔的整数 a 和 b，表示一个需要涂色的候选区间。

输出格式（输出至终端 / 标准输出）：

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

输入样例：

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

输出样例：

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≤100。
• 测试点 3-5 满足 N,Q≤5000。
• 测试点 6-10 中，输入数组不包含大于 10 的数。
• 测试点 11-20 没有额外限制。