K. Глючные робоанты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно директору Ресторана Отеля пришла в голову следующая мысль: «Все какое-то обычное. Надо что-то модернизировать!» Именно так и решили заменить всех официантов на роботов или, точнее, робоантов.

Но вот беда! Денег на закупку высококачественного оборудования не нашлось, и партия робоантов была заказана в ОАО «В Гараже у Петровича». И вот теперь, спустя неделю работы по непонятным причинам робоанты начали глючить. Проблема в том, что скоро в Отеле большой банкет. Для его проведения в Ресторане уже расставили $$$n$$$ столов и приготовили $$$n$$$ блюд. Все блюда попарно различны и имеют номера от $$$1$$$ до $$$n$$$. Изначально, блюда по мере готовности как-то расставили по $$$n$$$ столам, причем на каждый стол поставили только одно блюдо. Однако, к банкету необходимо расставить все на свои места, а именно, $$$i$$$-е блюдо должно оказаться на $$$i$$$-м столе.

Рядом с каждым столом изначально стоит робоант. Далее каждый робоант независимо от других может выполнять следующую операцию неограниченное число раз: пусть сейчас робоант стоит у $$$i$$$-го стола. Тогда, если у него с собой нет ни одного блюда, он может взять (а может и не брать) блюдо в данный момент, находящееся на $$$i$$$-м столе и перейти к любому $$$j$$$-му столу при условии, что $$$i$$$ и $$$j$$$ имеют общий делитель больший $$$1$$$. Далее, если у робоанта есть с собой блюдо, он может положить его на $$$j$$$-й стол (а может и не класть).

Теперь директор просит помочь ему у написать программу, которая определит, смогут ли его робоанты расставить все блюда по местам.

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество столиков в Ресторане.

Во-второй строке записано $$$n$$$ различных целых чисел $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le n$$$) — номера блюд изначально расставленных на соответственно $$$1$$$-й, $$$2$$$-й, ... $$$n$$$-й столиках.

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

Выведите «YES», если робоанты смогут расставить все блюда по местам, и «NO» в противном случае случае.

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

Рассмотрим первый пример: здесь расставить все по местам может один робоант, изначально стоящий у второго стола. Для этого он:

  1. Берёт со $$$2$$$-го стола $$$8$$$-е блюдо, перемещается к $$$8$$$-му столу, кладет блюдо.
  2. Берёт с $$$8$$$-го стола $$$2$$$-е блюдо, перемещается ко $$$2$$$-му столу, кладет блюдо.
  3. Перемещается к $$$4$$$-му столу.
  4. Берёт с $$$4$$$-го стола $$$6$$$-е блюдо, перемещается к $$$6$$$-му столу, кладет блюдо.
  5. Берёт с $$$6$$$-го стола $$$4$$$-е блюдо, перемещается к $$$4$$$-му столу, кладет блюдо.

Можно доказать, что во втором примере невозможно расставить все блюда по местам.