408799: GYM103325 C Банки дружбы

C. Банки дружбыограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Главные Психологи Береляндии обеспокоились тем, что жители страны практически перестали друг с другом общаться. Так что они разработали программу поддержки социальной активности населения под названием «Банки дружбы». Программа включала в себя основание $$$n$$$ новых банков, имеющих разные ставки по вкладам: за год вложенные в банк деньги увеличиваются в $$$x$$$ раз.

Каждый житель страны изначально получал виртуальную сумму — 1 единицу денег, которую можно вложить в любой из банков. Через год он мог забрать все деньги из этого банка и положить в другой, более выгодный, или же снова положить деньги в этот банк. Забранные из банка и никуда не вложенные деньги сгорают.

Такие выгодные условия сразу привлекли огромное количество вкладчиков. Но банки выставили неимоверные требования по условию вклада: нужно было собрать множество документов, справок, подписей и т.п. В итоге, чтобы сделать выгодные вложения, люди сутками стояли в очередях в банке и заводили знакомства, что повысило социальную активность береляндцев (в этом, собственно, и заключалась задумка психологов).

Через несколько лет было проведено исследование с целью узнать насколько эффективна программа «Банки дружбы». Были опрошены $$$q$$$ пар знакомых друг другу бреляндцев, которых попросили назвать текущие суммы их вкладов. После этого для каждой пары узнали, могли ли эти берляндцы познакомиться, когда брали вклад в каком-то из банков. Попробуйте узнать и вы.

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

В первой строке вводится число $$$n$$$ $$$(1 \le n \le 100\,000)$$$  — количество банков.

На следующей строке даны $$$n$$$ чисел $$$a_i$$$ $$$(2 \le a_i \le 100\,000)$$$ — во сколько раз увеличивается за год количество денег в $$$i$$$-м банке.

В третьей строке вводится число $$$q$$$ $$$(1 \le q \le 50\,000)$$$ — количество пар опрошенных берляндцев.

В следующих $$$q$$$ строках дано по два числа $$$x_i$$$ и $$$y_i$$$ $$$(1 \le x_i, y_i \le 100\,000)$$$ — суммы на счетах соответствующих берляндцев.

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

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

Система оценки

$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 34 & 1 \le n, q \le 1000 & \text {}\\ \hline 2 & 31 & 1 \le n, a_i \le 1000 & \text {}\\ \hline 3 & 35 & \text { Нет дополнительных ограничений } & \text {1, 2}\\ \hline \end{array}$$$$$$

ПримерВходные данные

3
2 3 7
4
15 5
2 7
35 175
15 9

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

NO
NO
YES
YES

Примечание

Тесты к этой задаче состоят из 3 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.