← 返回题目列表

Codeforces · 1707/E

E. 更换

中文机器翻译题面 查看原题

给定一个整数数组 $$$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)$$$。