Саша Белый давно планировал переехать в Кыштым. И вот настал день X. Саша собрал все свои вещи в ящики и вынес их на улицу. Ящики были распределены на n стопок, расположенных вдоль одной прямой, следующим образом: a
1 ящиков в первой стопке стоят непосредственно у газели, a
2 ящиков во второй стопке – правее первой на метр, следующие a
3 еще через метр и т.д. Теперь Белому нужно переставить все ящики как можно ближе к газели, а именно, все ящики из второй, третьей и т.д. стопок должны быть переставлены в первую стопку к исходным a
1 ящикам.
Саша за этот день уже очень устал. Но, к счастью, мимо проходили n мальчишек. Ребята согласились перенести ящики. Каждый из них, ввиду своей выносливости, переносит грузы следующим образом:
1. i-й мальчик проходится по стопкам, номера которых делятся на i, справа налево.
2. Он берет из первой стопки на своем пути ровно один ящик (эта стопка обязана быть непустой).
3. Пройдя i метров налево (то есть до следующей стопки, номер которой делится на i), он снова берет один ящик со стопки, рядом с которой он стоит (исходя из этого, в стопке обязательно должен быть хотя бы один ящик), пройдя еще i метров налево он снова берет ящик и так далее.
4. Когда i-й мальчик доходит до стопки с номером i, он кладет все ранее взятые ящики в эту стопку.
Каждый из ребят может делать сколько угодно проходов. Мальчики могут делать проходы в любом порядке (например, возможна ситуация, когда сначала проходится второй
мальчик, потом первый и снова второй).
Теперь Саша Белый хочет знать, получится ли у них переставить все ящики в начало. Скажите ему ответ на вопрос.
Входные данные
В первой строке входных данных записано целое число n количество стопок ящиков (1 <= n <= 10
5).
Во второй строке через пробел записаны n целых чисел di количество ящиков в i-й стопке (1 <= d
i <= 10
9).
Выходные данные
Выведите YES, если существует способ, при котором ребята перенесут все ящики к газели в первую стопку, или NO, если такого способа нет.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
2 1 3 5 3 |
YES |
| 2 |
4
1 5 2 3 |
NO |
Замечание
В первом примере сначала второй мальчик пройдется два раза, таким образом перенеся два ящика из четвертой стопки во вторую. После этого шага d = (2,3,3,3,3). Потом первый мальчик пройдется 3 раза, перетащив все ящики в первую стопку.
Во втором примере мальчикам не удастся перенести все ящики в первую стопку.