Хомяк Дима обожает грызть различные объекты, среди которых клетки, коробки, авторы плохих задач и даже деревья!
Недавно он обнаружил двоичное дерево поиска и тут же сгрыз все его ребра, в результате чего вершины дерева перемешались в случайном порядке. Дима знает, что если Андрей, который кропотливо строил дерево на протяжении долгого времени, придет и увидит, что все разрушено, то он очень расстроится. По счастью, прежде чем сгрызть все ребра, Дима заметил, что для любых двух вершин, соединенных ребром, наибольший общий делитель их значений превосходит $$$1$$$.
Помогите Диме восстановить любое подходящее двоичное дерево поиска или скажите, что это невозможно. Определение и свойства двоичного дерева поиска можно найти здесь.
В первой строке задано количество вершин $$$n$$$ ($$$2 \le n \le 700$$$).
В следующей строке через пробел следуют $$$n$$$ различных чисел $$$a_i$$$ ($$$2 \le a_i \le 10^9$$$) — значения в вершинах в отсортированном порядке.
Если можно собрать двоичное дерево поиска, такое что наибольший общий делитель любых двух вершин соединённых ребром больше $$$1$$$, выведите «Yes» (без кавычек).
В противном случае выведите «No» (без кавычек).
6
3 6 9 18 36 108
Yes
2
7 17
No
9
4 8 10 12 15 18 33 44 81
Yes
На картинке ниже проиллюстрировано одно из возможных деревьев для первого примера.
На картинке ниже проиллюстрировано одно из возможных деревьев для третьего примера.
