Sasha Bely recently got a job at a ski resort near Asha. First of all, he was assigned to install fences for the ski run.
Sasha was given n fences, each of length a
i. Any two consecutive fences are fastened to each other, but at the same time they can arbitrarily rotate relative to each other.
Sasha wants to make the track interesting: in his opinion, the track should be in the form of a spiral (fence number i +1 should be rotated 90 degrees clockwise relative to fence number i; at the same time, no fences, except adjacent ones, should not touch each other friend and intersect).
Unfortunately, not any set of fences can be folded into a spiral. Help Sasha determine for the given set whether it is possible to make a spiral out of it.
Input
The first line of the input contains an integer n — number of fences (1 <= n <= 10
5). The second line contains n space-separated integers a
i — length of i-th fence (1 <= a
i <=10
9).
Imprint
Print YES if it is possible to make a spiral out of these fences, or NO otherwise.
Examples
| # |
Input |
Output |
| 1 |
5
1 2 3 3 5
| YES |
| 2 |
6
5 7 6 8 6 10
| NO |
| 3 |
9
1 1 2 2 6 2 2 1 1
| YES |
Remark
Pay attention to the third example, the spiral can have two centers, the main thing is that the fences do not intersect. Illustration for the third example:
