20173번 - Imprecise Computer 다국어

The Imprecise Computer (IC) is a computer with some structural issue that it can compare two integers correctly only when their difference is at least two. For example, IC can always correctly answer ‘4 is larger than 2’, but it can answer either ‘2 is larger than 3’ or ‘3 is larger than 2’ (in this case, IC arbitrarily chooses one of them). For two integers x and y, we say ‘x defeats y’ when IC answers ‘x is larger than y’.

Given a positive integer n, let P_n = {1, 2, … , n} be the set of positive integers from 1 to n. Then we run a double round-robin tournament on P_n using IC. The double-round-robin tournament is defined as follows:

1. The tournament is composed of two rounds (the 1st round and the 2nd round).
2. For each round, each element in P_n is compared to every other element in P_n.

Now for each element k in P_n, let r_i(k) be the number of wins of k in the i-th round of the tournament. We also define the ‘difference sequence’ D = d₁d₂…d_n where for each 1 ≤ k ≤ n, d_k = |r₁(k) − r₂(k)|.

The following shows an example when n = 5.

In the example above, r₁(1) = 0, r₁(2) = 1, r₁(3) = 3, r₁(4) = 3, r₁(5) = 3, and r₂(1) = 1, r₂(2) = 1, r₂(3) = 1, r₂(4) = 3,r₂(5) = 4. Therefore, the difference sequence is D = 1 0 2 0 1 in this example.

Given a sequence of n nonnegative integers, write a program to decide whether the input sequence can be a difference sequence of P_n.

Your program is to read from standard input. The input starts with a line containing an integer n, (3 ≤ n ≤ 1,000,000), where n is the size of P_n. In the following line, a sequence of n integers between 0 and n is given, where each element in the sequence is separated by a single space.

Your program is to write to standard output. Print exactly one line. Print YES if the sequence can be the difference sequence of P_n, and print NO otherwise.