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

Назовём массив $$$b_1, b_2, \ldots, b_m$$$ ($$$m \ge 2$$$) хорошим, если его можно разрезать на две части так, чтобы все элементы в левой части были строго меньше, чем все элементы в правой части. Другими словами, должен существовать такой индекс $$$1 \le i < m$$$, что любой элемент из $$$b_1, \ldots, b_i$$$ строго меньше любого элемента из $$$b_{i+1}, \ldots, b_m$$$.

Дан массив $$$a_1, a_2, \ldots a_n$$$, состоящий из различных целых чисел от $$$1$$$ до $$$n$$$. Поступают $$$q$$$ запросов. В каждом запросе даны два числа $$$l$$$ и $$$r$$$. Требуется для каждого запроса проверить, является ли массив $$$a_l, a_{l+1}, \ldots, a_r$$$ хорошим.

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

Первая строка содержит единственное целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — размер массива.

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

Третья строка содержит единственное целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — описание $$$i$$$-го запроса.

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

Для каждого запроса выведите «Yes» (без кавычек), если массив $$$a_l, a_{l+1}, \ldots, a_r$$$ является хорошим, и «No» (без кавычек) иначе.

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

Примеры
Входные данные
5
3 2 1 4 5
5
1 5
1 3
1 4
1 2
2 5
Выходные данные
Yes
No
Yes
No
Yes
Входные данные
6
1 6 2 4 3 5
3
3 5
2 6
4 6
Выходные данные
Yes
No
Yes
Примечание

В первом примере:

  • Массив $$$[3,2,1,4,5]$$$ можно разрезать на две части $$$[3,2,1]$$$ и $$$[4,5]$$$.
  • Массив $$$[3,2,1]$$$ нельзя разрезать на две части так, чтобы все элементы в левой части были меньше всех элементов в правой части.
  • Массив $$$[3,2,1,4]$$$ можно разрезать на две части $$$[3,2,1]$$$ и $$$[4]$$$.
  • Массив $$$[3,2]$$$ нельзя разрезать на две части так, чтобы все элементы в левой части были меньше всех элементов в правой части.
  • Массив $$$[2,1,4,5]$$$ можно разрезать на две части $$$[2,1]$$$ и $$$[4,5]$$$.

Во втором примере:

  • Массив $$$[2,4,3]$$$ можно разрезать на две части $$$[2]$$$ и $$$[4,3]$$$.
  • Массив $$$[6,2,4,3,5]$$$ нельзя разрезать на две части так, чтобы все элементы в левой части были меньше всех элементов в правой части.
  • Массив $$$[4,3,5]$$$ можно разрезать на две части $$$[4,3]$$$ и $$$[5]$$$.