给定一个整数数组 $$$a_1,\ldots, a_n$$$,其中 $$$1\le a_i \le n$$$ 代表所有 $$$i$$$。
有一个“替换”函数 $$$f$$$,它接受一对整数 $$$(l, r)$$$(其中 $$$l \le r$$$)作为输入并输出一对 $$$$$$f\big( (l, r) \big)=\left(\min\{a_l,a_{l+1},\ldots,a_r\},\, \max\{a_l,a_{l+1},\ldots,a_r\}\right).$$$$$$
考虑重复调用此函数。也就是说,从起始对 $$$(l, r)$$$ 开始,我们得到 $$$f\big((l, r)\big)$$$,然后是 $$$f\big(f\big((l, r)\big)\big)$$$,然后是 $$$f\big(f\big(f\big((l, r)\big)\big)\big)$$$,依此类推。
现在您需要回答 $$$q$$$ 查询。对于第 $$$i$$$ 查询,您有两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$)。您必须回答必须对 $$$(l_i,r_i)$$$ 应用“替换”函数才能得到 $$$(1, n)$$$ 的最少次数,否则报告不可能。
输入
第一行包含两个正整数 $$$n$$$、$$$q$$$ ($$$1\le n,q\le 10^5$$$) — 序列 $$$a$$$ 的长度和查询的数量。
第二行包含 $$$n$$$ 正整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$) — 序列 $$$a$$$。
以下 $$$q$$$ 行中的每一行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — 查询。
输出
对于每个查询,输出所需的次数,如果不可能则输出$$$-1$$$。
示例
输入 #1
5 6 2 5 4 1 3 4 4 1 5 1 4 3 5 4 5 2 3
输出 #1
-1 0 1 2 3 4
输入 #2
6 3 2 3 4 6 1 2 5 6 2 5 2 3
输出 #2
5 1 3
输入 #3
5 3 3 2 2 4 1 2 5 1 3 1 5
输出 #3
-1 -1 0
注意
在第一个示例中,$$$n=5$$$ 和 $$$a=[2,5,4,1,3]$$$。
对于第一个查询:$$$(4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\ldots$$$,所以不可能得到$$$(1,5)$$$。
对于第二个查询,您已经有 $$$(1,5)$$$。
对于第三个查询:$$$(1,4)\to(1,5)$$$。
对于第四个查询:$$$(3,5)\to(1,4)\to(1,5)$$$。
对于第五个查询:$$$(4,5)\to(1,3)\to(2,5)\to(1,5)$$$。
对于第六个查询:$$$(2,3)\to(4,5)\to(1,3)\to(2,5)\to(1,5)$$$。