给定一个包含 $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"。
数据范围
- $1 \le n, q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a, b \le n$
样例
输入格式 1
6 3 3 1 4 1 5 9 4 1 3 3 2 5
输出格式 1
1 -1 2
说明 1
在第一个查询中，可以通过对前 4 个数字进行排序，仅用一次操作即可将数组排序。
在第二个查询中，无法通过现有操作将数组排序。
在第三个查询中，可以通过两次操作将数组排序：首先对前 2 个数字进行排序，然后对后 5 个数字进行排序。
子任务
| 子任务 | 数据范围 | 分值 |
|---|---|---|
| 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 |