题目描述

给定整数数组 $a_1,a_2,\ldots,a_n$，其中 $1\le a_i\le n$。

对于任意 $1\le l\le r\le n$，定义函数

$f(l,r)=\left(\min_{l\le i\le r}a_i,\ \max_{l\le i\le r}a_i\right)$。

现在从一个区间端点对 $(l,r)$ 开始，不断重复应用 $f$：

$(l_1,r_1)=f(l,r)$，

$(l_2,r_2)=f(l_1,r_1)$，

依此类推。

共有 $q$ 个互相独立的询问。对于每个初始对 $(l_i,r_i)$，求最少需要应用多少次 $f$ 才能到达 $(1,n)$。

如果永远无法到达 $(1,n)$，输出 -1。

注意：如果初始对本身就是 $(1,n)$，答案为 0。

输入格式

第一行两个整数 $n,q$，满足 $1\le n,q\le10^5$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $1\le a_i\le n$。

接下来 $q$ 行，每行两个整数 $l_i,r_i$，满足 $1\le l_i\le r_i\le n$。

输出格式

对于每个询问输出一行：

• 最少需要调用多少次 replace 才能得到 $(1,n)$；
• 若不可能，输出 -1。

样例 1

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

-1
0
1
2
3
4

例如：

• $(4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\cdots$，进入循环，所以答案为 -1；
• $(1,4)\to(1,5)$，答案为 1；
• $(3,5)\to(1,4)\to(1,5)$，答案为 2。

样例 2

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

5
1
3

样例 3

5 3
3 2 2 4 1
2 5
1 3
1 5

-1
-1
0

子任务