题目描述

给定一个长度为 $n$ 的整数数组 $x_1,x_2,\ldots,x_n$。

你需要回答 $q$ 个询问。对于一个询问 $(a,b)$，每次操作可以选择以下一种方式：

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

求使整个数组按非递减顺序排列所需的最少操作次数。如果无法做到，输出 -1。

每个询问都从给定的原始数组开始，询问之间互不影响。

输入格式

第一行包含两个整数 $n,q$，分别表示数组长度和询问数量。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$。

接下来 $q$ 行，每行包含两个整数 $a,b$，表示一个询问。

输出格式

输出 $q$ 行，每行包含一个整数，表示对应询问的最少操作次数；无法排序时输出 -1。

数据范围

对于所有测试数据：

• $1\le n,q\le 2\times 10^5$；
• $1\le x_i\le 10^9$；
• 每个询问均满足 $1\le a,b\le n$。

子任务

编号	分值	缩减范围	附加限制
1	6	$n,q\le 10$	所有询问均满足 $a+b\le n$
2	5		—
3	7	—	所有询问均满足 $a+b\le n$
4	14	$1\le x_i\le 2$	—
5	23	$n,q\le 5000$	数组是 $1,2,\ldots,n$ 的一个排列
6	12		—
7	33	—

样例 1

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

1
-1
2

样例 1 说明

第一个询问中，将前 $4$ 个数排序后得到 $[1,1,3,4,5,9]$，因此只需一次操作。

第二个询问中，两个可排序的区间互不相交。后半段的 $1$ 无法移动到前半段，所以无法将整个数组排序。

第三个询问中，先将前 $2$ 个数排序，得到 $[1,3,4,1,5,9]$；再将后 $5$ 个数排序，得到 $[1,1,3,4,5,9]$。单独执行任一种操作都不能完成排序，因此答案为 $2$。