Задача №115389. НВПБП
Подпоследовательность — это последовательность, которую можно получить из массива путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Например, последовательность \([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» иначе.
НВП массива \([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\).
7 5 1 2 5 4 7 3 6 6 7 4 6 3 3 3 5 4 7
YES YES YES YES NO