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。

输入输出样例 #1

输入 #1

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

输出 #1

1
-1
2

说明/提示

解释

在第一个询问中，可以通过对前 $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$

子任务

附加文件