Задача 43125. boxes

Sasha Bely had long planned to move to Kyshtym. And then the day X came. Sasha gathered all his things in boxes and took them out into the street. The boxes were distributed into n piles along one straight line, as follows: a₁ boxes in the first pile are directly next to the gazelle, a₂ boxes in the second pile &ndash ; to the right of the first one by a meter, the next a₃ one more meter, etc. Now White needs to rearrange all the boxes as close as possible to the gazelle, namely, all the boxes from the second, third, etc. stacks must be rearranged in the first stack to the original a₁ boxes.
Sasha was already very tired that day. But, fortunately, n boys passed by. The guys agreed to move the boxes. Each of them, due to its endurance, carries loads in the following way:
1. The i-th boy walks through piles divisible by i, from right to left.
2. He takes exactly one box from the first pile on his way (this pile must be non-empty).
3. After walking i meters to the left (that is, to the next pile, the number of which is divisible by i), he again takes one box from the pile next to which he stands (based on this, the pile must contain at least one box ), after walking i more meters to the left, he again takes the box and so on.
4. When the i-th boy reaches the pile with number i, he puts all the previously taken boxes into this pile.

Each of the guys can make as many passes as they want. Boys can make passes in any order (for example, it is possible that the second
boy, then the first and again the second).
Now Sasha Bely wants to know if they can rearrange all the boxes to the beginning. Tell the answer to the question.

Input
The first line of the input contains an integer n the number of stacks of boxes (1 <= n <= 10⁵).
The second line contains n space-separated integers di the number of boxes in the i-th pile (1 <= d_i <= 10⁹).
Imprint
Print YES if there is a way in which the guys will move all the gazelle boxes to the first pile, or NO if there is no such way.

Examples

#	Input	Output
1	5 2 1 3 5 3	YES
2	4 1 5 2 3	NO

Remark
In the first example, first the second boy walks twice, thus transferring two boxes from the fourth pile to the second. After this step d = (2,3,3,3,3). Then the first boy will walk 3 times, dragging all the boxes to the first pile.
In the second example, the boys will not be able to move all the boxes to the first pile.