Monsters
Limits: 1 sec., 256 MiB
Zenyk is a huge video games fan. In one of the most important stages of the game he’s playing now, there are \(n\) monsters located on a straight line, and the \(i\)-th mosters is located at position \(x_i\). The goal of the game is to kill exactly \(n-2\) monsters, capture the rest and take them to interrogation.
But it’s not that easy, because he is not allowed to just kill any monster any time. He can kill the \(i\)-th monster if and only if the two adjacent alive monsters exist and are equidistant from \(x_i\). In other words, the distance from the \(i\)-th monster to the left alive neighbour should be the same as the distance to the right alive neighbour.
You are given the positions of the monsters. Your task is to determine whether Zenyk can kill \(n-2\) monsters to finish the game.
Input
The first line contains a single integer \(n\) — the initial number of monsters. The second line contains \(n\) space-separated integers \(x_i\), which are the positions of the monsters. No two monsters are located at the same point.
Output
In the only line print "YES"
if Zenyk can achive his
goal, and "NO"
otherwise (without quotes).
Constraints
\(2 \le n \le 10^5\),
\(0 \le x_i \le 10^9\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4 0 1 4 2 | YES |
Input (stdin) | Output (stdout) |
---|---|
3 7 0 4 | NO |
Notes
In the first sample, Zenyk can kill the 2nd monster first (which is located at position 1, and the adjacent alive monsters are at positions 0 and 2). After that, Zenyk can kill the 4th monsters (which is located at position 2, and the adjacent alive monsters are at positions 0 and 4).
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|