#5717. 「BalticOI 2026」排序

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 BalticOI 2026 Day2「Sort」

给定一个包含 $n$ 个整数的数组 $x_{1}, x_{2}, \ldots, x_{n}$。你需要回答 $q$ 个询问 $(a, b)$。在每次操作中，你可以选择以下两种操作之一：

• 将前 $a$ 个数字按非递减顺序排序；
• 将最后 $b$ 个数字按非递减顺序排序。

请问将整个数组按非递减顺序排序所需的最少操作次数是多少？对于每个询问，数组都从初始值 $x_{1}, x_{2}, \ldots, x_{n}$ 开始。

输入格式

第一行包含两个整数 $n$ 和 $q$，表示数组的长度和询问次数。

第二行包含 $n$ 个整数 $x_{1}, x_{2}, \ldots, x_{n}$，表示数组的初始内容。

接下来的 $q$ 行描述询问，每行包含两个整数 $a$ 和 $b$。

输出格式

输出 $q$ 行，对应每个询问的答案。如果无法将数组排序，则输出 $-1$。

样例

输入

6 3
3 1 4 1 5 9
4 1
3 3
2 5

输出

1
-1
2

在第一个询问中，可以通过对前 $4$ 个数字进行一次排序，从而将数组排序。

在第二个询问中，无法通过可用的操作将数组排序。

在第三个询问中，可以通过两次操作将数组排序：首先对前 $2$ 个数字进行排序，然后对最后 $5$ 个数字进行排序。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n, q \leq 2 \cdot 10^{5}$
• $1 \leq x_{i} \leq 10^{9}$
• 在所有询问中，$1 \leq a, b \leq n$

详细子任务附加限制及分值如下表所示。