CF2138B Antiamuny Wants to Learn Swap

For an array $$$b$$$ of length $$$m$$$, you may perform the following two operations: 1. Select an index $$$1\\le i\\le m - 1$$$. Then, swap the values of $$$b\_i$$$ and $$$b\_{i + 1}$$$. 2. Select an index $$$1\\le i\\le m - 2$$$. Then, swap the values of $$$b\_i$$$ and $$$b\_{i + 2}$$$. However, you can only perform operation $$$2$$$ at most once.We define $$$f(b)$$$ as the minimum number of operations (using both operation 1 and operation 2) required to sort array $$$b$$$ in non-decreasing order, and $$$g(b)$$$ as the minimum number of operations required to sort array $$$b$$$ in non-decreasing order using only operation 1. The array $$$b$$$ is perfect if $$$f(b) = g(b)$$$. In other words, the ability to use operation 2 does not reduce the number of operations required to sort array $$$b$$$ compared to using only adjacent swaps. You are given a permutation $$$a$$$ of length $$$n$$$$$$^{\\text{∗}}$$$, and must answer $$$q$$$ queries. Each query consists of two integers $$$l$$$ and $$$r$$$ ($$$1\\le l\\le r\\le n$$$), representing the subarray $$$a\[l\\ldots r\]$$$$$$^{\\text{†}}$$$. For each query, determine whether the subarray $$$a\[l\\ldots r\]$$$ is perfect. $$$^{\\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$\[2,3,1,5,4\]$$$ is a permutation, but $$$\[1,2,2\]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$\[1,3,4\]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array). $$$^{\\text{†}}$$$The subarray $$$a\[l\\ldots r\]$$$ includes all elements from index $$$l$$$ to $$$r$$$, i.e., $$$\[a\_l, a\_{l + 1}, a\_{l + 2}, \\ldots, a\_r\]$$$.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \\le t \\le 5 \\cdot 10^4$$$). The description of the test cases follows. The first line of each test case contains two integers $$$n$$$, $$$q$$$ ($$$1 \\le n, q \\le 5 \\cdot 10^5$$$) — the length of array $$$a$$$ and the number of queries. The second line of each test case contains $$$n$$$ integers $$$a\_1, a\_2, \\ldots ,a\_n$$$ ($$$1 \\le a\_i \\le n$$$) — the elements in permutation $$$a$$$. Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \\leq l \\leq r \\leq n$$$) — the left and right endpoints of the queried subarray. It is guaranteed that both the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$5\\cdot 10^5$$$.

For each test case, output "YES" if queried subarray $$$a\[l\\ldots r\]$$$ is perfect, and "NO" otherwise. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

In the first test case: - Query 1: $$$a\[1\\ldots 2\] = \[1, 5\]$$$ is already sorted in increasing order. Thus, $$$f(a\[1\\ldots 2\]) = g(a\[1\\ldots 2\]) = 0$$$ and the subarray $$$a\[1\\ldots 2\]$$$ is perfect. - Query 2: $$$a\[1\\ldots 5\] = \[1, 5, 4, 3, 2\]$$$. $$$f(a\[1\\ldots 5\]) = 4$$$ as we can sort the array using the following sequence of operations:$$$$$$\[1,\\textbf{5},4,\\textbf{3},2\] \\xrightarrow{\\text{op} 2} \[1,3,4,\\textbf{5},\\textbf{2}\] \\xrightarrow{\\text{op} 1} \[1,3,\\textbf{4},\\textbf{2},5\]\\xrightarrow{\\text{op} 1} \[1,\\textbf{3},\\textbf{2},4,5\] \\xrightarrow{\\text{op} 1}\[1,2,3,4,5\]$$$$$$ On the other hand, $$$g(a\[1\\ldots 5\]) = 6$$$ as it requires at least $$$6$$$ adjacent swaps to sort $$$a\[1\\ldots 5\]$$$. Since $$$f(a\[1\\ldots 5\]) \\neq g(a\[1\\ldots 5\])$$$, the subarray $$$a\[1\\ldots 5\]$$$ is not perfect. - Query 3: $$$a\[3\\ldots 5\] = \[4, 3, 2\]$$$. $$$f(a\[3\\ldots 5\]) = 1$$$ as we can sort the array using the following sequence of operations:$$$$$$\[\\textbf{4}, 3,\\textbf{2}\] \\xrightarrow{\\text{op} 2} \[2, 3, 4\]$$$$$$ On the other hand, $$$g(a\[3\\ldots 5\]) = 3$$$ as it requires at least $$$3$$$ adjacent swaps to sort $$$a\[3\\ldots 5\]$$$. Since $$$f(a\[3\\ldots 5\]) \\neq g(a\[3\\ldots 5\])$$$, the subarray $$$a\[3\\ldots 5\]$$$ is not perfect.