P16362 [BalticOI 2026] Sort

给定一个包含 $n$ 个整数的数组 $x_1, x_2, \dots, x_n$。你需要回答 $q$ 个询问 $(a, b)$。每次操作中，你可以执行以下两种操作之一： - 将前 $a$ 个数按非递减序排序，或 - 将后 $b$ 个数按非递减序排序。 若要使得整个数组按非递减序排列，至少需要多少次操作？在每个询问中，数组均从初始值 $x_1, x_2, \dots, x_n$ 开始。

第一行包含两个整数 $n$ 和 $q$，分别表示数组的长度和询问的数量。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示数组的内容。 接下来的 $q$ 行描述各询问。每行包含两个整数 $a$ 和 $b$。

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

### 解释 在第一个询问中，可以通过对前 $4$ 个数排序，在一次操作内将数组排序。 在第二个询问中，无法利用给定的操作将数组排序。 在第三个询问中，可以通过两次操作将数组排序：首先对前 $2$ 个数排序，然后对后 $5$ 个数排序。 ### 数据范围 - $1 \le n,q \le 2 \cdot 10^5$ - $1 \le x_i \le 10^9$ - 所有询问中 $1 \le a,b \le n$ ### 子任务 | 子任务 | 约束条件 | 分值 | | :---: | --- | :---: | | 1 | $n,q\le 10$ 且所有询问满足 $a+b\le n$ | $6$ | | 2 | $n,q \le 10$ | $5$ | | 3 | 所有询问满足 $a+b \le n$ | $7$ | | 4 | $1 \le x_i \le 2$ | $14$ | | 5 | $n,q \le 5000$ 且数组是 $1,2,\dots,n$ 的一个排列 | $23$ | | 6 | $n,q \le 5000$ | $12$ | | 7 | 无额外限制 | $33$ | 翻译由 DeepSeek V4 Pro 完成