C. Поезд и запросы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдоль железной дороги расположены станции, пронумерованные от $$$1$$$ до $$$10^9$$$. Скорый поезд всегда едет по маршруту, состоящему из $$$n$$$ станций $$$u_1, u_2, \dots, u_n$$$, где ($$$1 \le u_i \le 10^9$$$). Поезд едет по маршруту слева направо. Он начинает свой путь на станции $$$u_1$$$, затем останавливается на станции $$$u_2$$$, затем на $$$u_3$$$ и так далее. Станция $$$u_n$$$ — конечная.

Допустимо, что поезд посетит одну станцию более одного раза. То есть среди чисел $$$u_1, u_2, \dots, u_n$$$ могут быть дубликаты.

Вам даны $$$k$$$ запросов, каждый из которых содержит два различных целых числа $$$a_j$$$ и $$$b_j$$$ ($$$1 \le a_j, b_j \le 10^9$$$). Для каждого запроса необходимо определить, можно ли доехать на поезде от станции с номером $$$a_j$$$ до станции с номером $$$b_j$$$.

Например, пусть маршрут поезда состоит из $$$6$$$ станций с номерами [$$$3, 7, 1, 5, 1, 4$$$] и даны $$$3$$$ следующих запроса:

  • $$$a_1 = 3$$$, $$$b_1 = 5$$$

    Доехать от станции $$$3$$$ до станции $$$5$$$ можно, проехав по участку маршрута, состоящего из станций [$$$3, 7, 1, 5$$$]. Ответ: YES.

  • $$$a_2 = 1$$$, $$$b_2 = 7$$$

    Доехать от станции $$$1$$$ до станции $$$7$$$ нельзя, так как поезд не может ехать в обратном направлении. Ответ: NO.

  • $$$a_3 = 3$$$, $$$b_3 = 10$$$

    Доехать от станции $$$3$$$ до станции $$$10$$$ нельзя, так как станция $$$10$$$ не входит в маршрут поезда. Ответ: NO.

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

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

Далее следуют описания наборов входных данных.

Первая строка каждого набора пустая.

Во второй строке каждого набора входных данных содержится два целых числа: $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5$$$) — количество станций, из которых состоит маршрут поезда и количество запросов соответственно.

В третьей строке каждого набора входных данных записано ровно $$$n$$$ целых чисел $$$u_1, u_2, \dots, u_n$$$ ($$$1 \le u_i \le 10^9$$$). Числа $$$u_1, u_2, \dots, u_n$$$ необязательно различны.

В следующих $$$k$$$ строках содержатся два различных целых числа $$$a_j$$$ и $$$b_j$$$ ($$$1 \le a_j, b_j \le 10^9$$$), описывающие запрос с номером $$$j$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превышает $$$2 \cdot 10^5$$$. Аналогично гарантируется, что сумма значений $$$k$$$ по всем наборам входных данных в тесте также не превышает $$$2 \cdot 10^5$$$.

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

Для каждого запроса в каждом наборе входных данных в отдельной строке выведите:

  • YES, если на поезде можно доехать от станции $$$a_j$$$ до станции $$$b_j$$$.
  • NO в противном случае.

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

Пример
Входные данные
3

6 3
3 7 1 5 1 4
3 5
1 7
3 10

3 3
1 2 1
2 1
1 2
4 5

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

Первый набор входных данных разобран в условии задачи.