F. Орангутано-одобренный массив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, у вас есть массив $$$b$$$. Изначально у вас также есть множество $$$S$$$, которое содержит все различные элементы массива $$$b$$$. Массив $$$b$$$ называется орангутано-одобренным, если его можно сделать пустым, выполняя следующую операцию:

  • Выбрать индексы $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq |b|$$$) такие, что $$$v = b_l = b_{l+1} = \ldots = b_r$$$ и $$$v$$$ присутствует в $$$S$$$. Удалить $$$v$$$ из $$$S$$$, а также удалить все $$$b_i$$$, для которых $$$l \leq i \leq r$$$. Затем подвинуть элементы $$$b_{r+1}, b_{r+2}, \ldots$$$ влево на позиции $$$b_l, b_{l+1}, \ldots$$$ соответственно.

Вам дан массив $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов.

Каждый запрос состоит из двух индексов $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), и вам нужно определить, является ли подмассив $$$a_{l}, a_{l+1}, \ldots, a_r$$$ орангутано-одобренным.

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

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

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

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива $$$a$$$.

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

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

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

Для каждого запроса выведите «YES» (без кавычек), если подмассив от $$$l$$$ до $$$r$$$ является орангутано-одобренным, и «NO» (без кавычек) в противном случае.

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

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

В первом запросе первого набора входных данных ответ — YES.

  • Изначально $$$S=\{1,2\}$$$ и $$$b=[1,2,2,1]$$$.
  • Выберите $$$l=2$$$ и $$$r=3$$$. Поскольку $$$b_2=b_3=2$$$ находится в $$$S$$$, мы можем удалить $$$b_2$$$ и $$$b_3$$$ из массива, а также удалить $$$2$$$ из $$$S$$$. Множество $$$S$$$ становится $$$\{1\}$$$, а массив — $$$[1,1]$$$.
  • Выберите $$$l=1$$$ и $$$r=2$$$. Поскольку $$$b_1=b_2=1$$$ находится в $$$S$$$, мы можем удалить $$$b_1$$$ и $$$b_2$$$ из массива, а также удалить $$$1$$$ из $$$S$$$. Множество $$$S$$$ становится $$$\{\}$$$, а массив — $$$[]$$$.
  • Поскольку массив теперь пуст, мы можем сказать, что исходный массив — орангутано-одобренный

В первом запросе второго набора входных данных ответ — NO, потому что можно показать, что подмассив $$$[2,1,2,1]$$$ не может стать пустым ни при какой последовательности корректных операций.