B. Антиамуни хочет научиться обменам
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b$$$ длины $$$m$$$ вы можете выполнять следующие две операции:

  1. Выберите индекс $$$1\le i\le m - 1$$$. Затем обменяйте значения $$$b_i$$$ и $$$b_{i + 1}$$$.
  2. Выберите индекс $$$1\le i\le m - 2$$$. Затем обменяйте значения $$$b_i$$$ и $$$b_{i + 2}$$$.
Однако операцию $$$2$$$ можно выполнять не более одного раза.

Определим $$$f(b)$$$ как минимальное количество операций (с использованием как операции 1, так и операции 2), необходимых для сортировки массива $$$b$$$ в неубывающем порядке, и $$$g(b)$$$ как минимальное количество операций, необходимых для сортировки массива $$$b$$$ в неубывающем порядке только с использованием операции 1.

Массив $$$b$$$ является совершенным, если $$$f(b) = g(b)$$$. Другими словами, возможность использования операции 2 не уменьшает количество операций, необходимых для сортировки массива $$$b$$$ по сравнению с использованием только соседних обменов.

Вам дана перестановка $$$a$$$ длины $$$n$$$$$$^{\text{∗}}$$$, и вы должны ответить на $$$q$$$ запросов. Каждый запрос состоит из двух целых чисел $$$l$$$ и $$$r$$$ ($$$1\le l\le r\le n$$$), представляющих подмассив $$$a[l\ldots r]$$$$$$^{\text{†}}$$$. Для каждого запроса определите, является ли подмассив $$$a[l\ldots r]$$$ совершенным.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Подмассив $$$a[l\ldots r]$$$ включает все элементы от индекса $$$l$$$ до $$$r$$$, т.е. $$$[a_l, a_{l + 1}, a_{l + 2}, \ldots, a_r]$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^5$$$) — длина массива $$$a$$$ и количество запросов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots ,a_n$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки $$$a$$$.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — левые и правые границы запрашиваемого подмассива.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$5\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если запрашиваемый подмассив $$$a[l\ldots r]$$$ является совершенным, и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
2
5 5
1 5 4 3 2
1 2
1 5
3 5
1 4
2 5
5 5
3 2 1 4 5
1 1
4 5
1 4
2 5
3 4
Выходные данные
YES
NO
NO
NO
NO
YES
YES
NO
YES
YES
Примечание

В первом наборе входных данных из примера:

  • Запрос 1: $$$a[1\ldots 2] = [1, 5]$$$ уже отсортирован в порядке возрастания. Таким образом, $$$f(a[1\ldots 2]) = g(a[1\ldots 2]) = 0$$$ и подмассив $$$a[1\ldots 2]$$$ является совершенным.
  • Запрос 2: $$$a[1\ldots 5] = [1, 5, 4, 3, 2]$$$. $$$f(a[1\ldots 5]) = 4$$$, так как мы можем отсортировать массив, используя следующую последовательность операций:

    $$$$$$[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]$$$$$$

    С другой стороны, $$$g(a[1\ldots 5]) = 6$$$, так как требуется как минимум $$$6$$$ соседних обменов для сортировки $$$a[1\ldots 5]$$$. Поскольку $$$f(a[1\ldots 5]) \neq g(a[1\ldots 5])$$$, подмассив $$$a[1\ldots 5]$$$ не является совершенным.

  • Запрос 3: $$$a[3\ldots 5] = [4, 3, 2]$$$. $$$f(a[3\ldots 5]) = 1$$$, так как мы можем отсортировать массив, используя следующую последовательность операций:

    $$$$$$[\textbf{4}, 3,\textbf{2}] \xrightarrow{\text{op} 2} [2, 3, 4]$$$$$$

    С другой стороны, $$$g(a[3\ldots 5]) = 3$$$, так как требуется как минимум $$$3$$$ соседних обмена для сортировки $$$a[3\ldots 5]$$$. Поскольку $$$f(a[3\ldots 5]) \neq g(a[3\ldots 5])$$$, подмассив $$$a[3\ldots 5]$$$ не является совершенным.