美术课上，小 A 收到了一盒特殊的水彩，共有 N 种不同的色号，色号值 1 \sim N，色号值越大，颜色越深。（接下来，我们会用颜色 i 表示色号值为 i 的颜色）

美术老师给同学们发了一张长条状未涂色的美术纸，美术纸被均匀的分为了 N 个小方格，小方格的编号为 1 \sim N。

老师要求同学们涂色时遵循如下的要求：

• 每次涂色，需要选中连续若干个相邻的小方格，并涂上同一个色号的颜色。
• 同一个小方格，可以多次涂色，但只能用大色号覆盖小色号，不允许用小色号覆盖大色号。

比如：如果 7 个小方格最终要涂成 1 3 2 3 2 3 1 这样的色号，可以通过如下 5 次涂色步骤实现。

• 第 1 次涂色：将 [1, 7] 涂成颜色 1，得到 1 1 1 1 1 1 1。
• 第 2 次涂色：将 [3, 5] 涂成颜色 2，得到 1 1 2 2 2 1 1。
• 第 3 次涂色：将 [2, 2] 涂成颜色 3，得到 1 3 2 2 2 1 1。
• 第 4 次涂色：将 [4, 4] 涂成颜色 3，得到 1 3 2 3 2 1 1。
• 第 5 次涂色：将 [6, 6] 涂成颜色 3，得到 1 3 2 3 2 3 1。

老师给出了 N 个小方格最终涂好色之后每个小方格的颜色值，要求小 A 按上述要求进行涂色。但由于时间关系，老师不要求小 A 完成 N 个小方格的涂色，只需要小 A 从 M 个区间中任选一个区间进行涂色。

聪明的小 A 想到，如果选择一个涂色次数最小的区间来涂色，会比较省时省力。因此小 A 请你帮他先计算出这 M 个区间，每个区间的最少涂色次数。

第 1 行输入两个整数 N 和 M。

第 2 行输入 N 个整数，表示老师给出的 N 个小方格最终的颜色值。

接下来 M 行，每行给出两个整数 L_j, R_j 表示第 j 次询问的区间。

输出 M 个整数，代表 M 个区间，每个区间的最少涂色次数。

请注意：每次询问都没有真正涂色，只是假设如果选择这个区间，请你求出涂色次数。

样例解释 1

第 1 个区间，选择 [1, 4]，即选择最终颜色为 1 3 2 2 这 4 个小方格进行涂色，最少需要涂色 3 次。

• 第 1 次涂色：将 [1, 1] 涂成颜色 1，得到 1 0 0 0。（未涂色的位置用颜色 0 表示）
• 第 2 次涂色：将 [3, 4] 涂成颜色 2，得到 1 0 2 2。
• 第 3 次涂色：将 [2, 2] 涂成颜色 3，得到 1 3 2 2。

第 2 个区间，选择 [3, 4]，即选择最终颜色为 2 2 这 2 个小方格进行涂色，最少需要涂色 1 次。

• 第 1 次涂色：将 [3, 4] 涂成颜色 2，得到 2 2。

第 3 个区间，选择 [4, 7]，即选择最终颜色为 2 3 2 2 这 4 个小方格进行涂色，最少需要涂色 2 次。

• 第 1 次涂色：将 [4, 7] 涂成颜色 2，得到 2 2 2 2。
• 第 2 次涂色：将 [5, 5] 涂成颜色 3，得到 2 3 2 2。

第 4 个区间，选择 [2, 5]，即选择最终颜色为 3 2 2 3 这 4 个小方格进行涂色，最少需要涂色 3 次。

• 第 1 次涂色：将 [2, 5] 涂成颜色 2，得到 2 2 2 2。
• 第 2 次涂色：将 [2, 2] 涂成颜色 3，得到 3 2 2 2。
• 第 3 次涂色：将 [5, 5] 涂成颜色 3，得到 3 2 2 3。

第 5 个区间，选择 [1, 9]，即选择最终颜色为 1 3 2 2 3 2 2 3 1 这 9 个小方格进行涂色，最少需要涂色 5 次。

• 第 1 次涂色：将 [1, 9] 涂成颜色 1，得到 1 1 1 1 1 1 1 1 1。
• 第 2 次涂色：将 [3, 7] 涂成颜色 2，得到 1 1 2 2 2 2 2 1 1。
• 第 3 次涂色：将 [2, 2] 涂成颜色 3，得到 1 3 2 2 2 2 2 1 1。
• 第 4 次涂色：将 [5, 5] 涂成颜色 3，得到 1 3 2 2 3 2 2 1 1。
• 第 5 次涂色：将 [8, 8] 涂成颜色 3，得到 1 3 2 2 3 2 2 1 3。

样例 4

见选手目录下的 table/table4.in 与 table/table4.ans。

数据范围

对于所有测试数据，均满足 1 \le N, M \le 2 \times 10^5，1 \le L_j, R_j \le N，N 个小方格最终涂色的值 1 \le A_i \le N。

特殊性质A：A_i 只有 5 种不同的值，每种数值有 1000 个，且相同的数值一定相邻。

特殊性质B：1 \le A_i \le 10。

月赛线段树树状数组25年5月