B. Antiamuny Wants to Learn Swaptime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output For an array $$$b$$$ of length $$$m$$$, you may perform the following two operations: Select an index $$$1\le i\le m - 1$$$. Then, swap the values of $$$b_i$$$ and $$$b_{i + 1}$$$. 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]$$$.InputEach 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$$$.OutputFor 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. ExampleInput25 51 5 4 3 21 21 53 51 42 55 53 2 1 4 51 14 51 42 53 4OutputYES
NO
NO
NO
NO
YES
YES
NO
YES
YES
NoteIn 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.