Подпоследовательность — это последовательность, которую можно получить из массива путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Например, последовательность $$$[1, 3, 6]$$$ — это подпоследовательность массива $$$[1, 2, 3, 6, 4, 5]$$$. Длиной подпоследовательности называют количество элементов в ней.
Наибольшая возрастающая подпоследовательность (НВП) — это подпоследовательность массива наибольшей длины, каждый следующий элемент которой строго больше предыдущего.
Для массива $$$a$$$ длины $$$n$$$ определим $$$\overline{a_{[l, r]}}$$$ как $$$a_1, \ldots, a_{l - 1}, a_{r+1}, \ldots, a_{n}$$$, то есть весь массив за исключением подотрезка $$$[l, r]$$$.
Наибольшая возрастающая подпоследовательность без подотрезка $$$[l, r]$$$ (НВПБП) — наибольшая возрастающая подпоследовательность массива $$$\overline{a_{[l, r]}}$$$. Обозначим длину этой НВПБП за $$$f(\overline{a_{[l, r]}})$$$.
Дан массив $$$a$$$ длины $$$n$$$. Пусть длина его НВП равна $$$f(a)$$$. Необходимо ответить на $$$q$$$ запросов. Каждый запрос задается парой чисел $$$l, r$$$. В ответ на запрос необходимо вывести, выполняется ли равенство $$$f(a) = f(\overline{a_{[l, r]}})$$$.
В первой строке ввода находятся два целых числа $$$n, q$$$ — длина массива $$$a$$$ и число запросов. $$$(1 \leq n, q \leq 4\cdot 10^5)$$$.
Во второй строке ввода находятся $$$n$$$ целых чисел — массив $$$a$$$. $$$(1 \leq a_{i} \leq 10^{9})$$$.
В следующих $$$q$$$ строках находятся по два целых числа $$$l_{i}$$$ и $$$r_{i}$$$ — запросы. $$$(1 \leq l_{i} \leq r_{i} \leq n)$$$.
Выведите $$$q$$$ строк. В $$$i$$$-й строке выведите «YES» (без кавычек), если $$$f(a)=f(\overline{a_{[l_i, r_i]}})$$$, и «NO» иначе.
7 51 2 5 4 7 3 66 74 63 33 54 7
YES YES YES YES NO
НВП массива $$$[1, 2, 5, 4, 7, 3 ,6]$$$ равна $$$[1, 2, 5, 7]$$$, то есть длина равна $$$4$$$.
В первом запросе $$$\overline{a_{[6, 7]}} = [1, 2, 5, 4, 7]$$$. Во втором запросе $$$\overline{a_{[4, 6]}} = [1, 2, 5, 6]$$$. Очевидно, что $$$f(a) = f(\overline{a_{[6, 7]}}) = f(\overline{a_{[4, 6]}}) = 4$$$.
