G. Разделимые подмассивы
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Технически это интерактивная задача.

Назовем массив $$$a$$$ из $$$m$$$ чисел разделимым, если выполняется хотя бы одно условие:

  • Существует такой индекс $$$i$$$ ($$$1 \le i \lt m$$$) и такое целое число $$$x$$$, что для любого индекса $$$j$$$ ($$$j \le i$$$) выполняется $$$a_{j} \le x$$$ и для любого индекса $$$k$$$ ($$$k \gt i$$$) выполняется $$$a_{k} \gt x$$$.
  • Существует такой индекс $$$i$$$ ($$$1 \le i \lt m$$$) и такое целое число $$$x$$$, что для любого индекса $$$j$$$ ($$$j \le i$$$) выполняется $$$a_{j} \gt x$$$ и для любого индекса $$$k$$$ ($$$k \gt i$$$) выполняется $$$a_{k} \le x$$$.

Вам дана перестановка $$$p$$$ натуральных чисел $$$1, 2, \dots, n$$$. Ваша задача быстро уметь отвечать на запросы вида: оставим от перестановки только отрезок [$$$l$$$, $$$r$$$], то есть числа $$$p_{l}, p_{l + 1}, \dots, p_{r}$$$, тогда является ли этот подмассив чисел разделимым?

Запросы будут подаваться в интерактивном режиме группами по $$$10$$$ штук, то есть вы не получите следующую группу запросов до тех пор, пока не выведете все ответы для текущей группы.

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$p_{i}$$$ ($$$1 \le p_{i} \le n$$$) — сама перестановка натуральных чисел.

Третья строка содержит одно натуральное число $$$q$$$ ($$$10 \le q \le 10^{6}, q \bmod 10 = 0$$$) — количество запросов.

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

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

Для каждого запроса выведите строку «YES», если подмассив из этого запроса разделимый и «NO» иначе.

После вывода ответов на группу запросов не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Вы должны обязательно сбросить буфер после $$$10$$$-го, $$$20$$$-го, $$$30$$$-го запроса (и так далее), то есть после каждого запроса, номер которого делится на $$$10$$$. После этого можно будет считывать следующую группу запросов.

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