Репликанты регулярно проходят проверку эмоционального состояния и стабильности, чтобы люди были уверены, что репликанты не начнут действовать им во вред.
В 2048-м году наконец-то решили эту проверку расширить и включить в нее оценку умственных и вычислительных способностей репликантов, чтобы вовремя выявлять проблемы, связанные с их повреждениями. Одно из заданий, проверяющих уровень логики и арифметических способностей, выглядит следующим образом.
Репликанту показывают массив целых чисел $$$a$$$ длины $$$n$$$, после чего просят ответить только «да» или «нет» на вопрос: правда ли, что значение $$$$$$\mathtt{gcd}(a_1, a_2, \ldots, a_n)!$$$$$$ совпадает со значением $$$$$$\mathtt{gcd}(a_1!, a_2!, \ldots, a_n!) \text{.}$$$$$$
Здесь за $$$\mathtt{gcd}$$$ обозначен наибольший общий делитель набора чисел, а восклицательным знаком обозначен факториал числа.
Помогите Кею пройти проверку, сообщив ему ответ на вопрос для данного массива.
В первой строке ввода дано целое число $$$n$$$ — длина массива ($$$1 \le n \le 10^5$$$).
Во второй строке перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы массива ($$$1 \le a_i \le 10^9$$$).
Выведите «YES» в любом регистре без кавычек, если два данных выражения принимают одно и то же значение, и «NO» иначе.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
0 | – | примеры из условия | полная | |
1 | 20 | $$$a_i \le 10$$$ | полная | |
2 | 15 | $$$n \le 2$$$ | первая ошибка | |
3 | 15 | $$$n \le 3$$$ | 2 | первая ошибка |
4 | 10 | все $$$a_i$$$ — простые | первая ошибка | |
5 | 40 | нет | 0 – 4 | первая ошибка |
51 2 3 4 5
YES
36 30 15
NO
В первом примере значение обоих выражений равно $$$1$$$, так как в обоих случаях под $$$\mathtt{gcd}$$$ находится единица.
Во втором примере данные выражения принимают значения $$$6$$$ и $$$720$$$, соответственно.