407895: GYM102920 E Imprecise Computer

Memory Limit：512 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

E. Imprecise Computertime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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, \ldots, n\}$$$ be the set of positive integers from $$$1$$$ to $$$n$$$. Then we run a double round-robin tournament on Pn using IC. The double-round-robin tournament is defined as follows:

The tournament is composed of two rounds (the $$$1^{\text{st}}$$$ round and the $$$2^{\text{nd}}$$$ round). 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_1d_2 \ldots d_n$$$ where for each $$$1 \leq k \leq n$$$, $$$d_k = |r_1(k) − r_2(k)|$$$.

The following shows an example when $$$n = 5$$$.

$$$$$$ \begin{array}{ |c|c| } \hline \textbf{1st round} & \textbf{2nd round} \cr \hline \texttt{2 defeats 1} & \texttt{3 defeats 1} \\ \texttt{3 defeats 1} & \texttt{4 defeats 1} \\ \texttt{4 defeats 1} & \texttt{5 defeats 1} \\ \texttt{5 defeats 1} & \texttt{1 defeats 2} \\ \texttt{3 defeats 2} & \texttt{4 defeats 2} \\ \texttt{4 defeats 2} & \texttt{5 defeats 2} \\ \texttt{5 defeats 2} & \texttt{2 defeats 3} \\ \texttt{5 defeats 3} & \texttt{4 defeats 3} \\ \texttt{3 defeats 4} & \texttt{5 defeats 3} \\ \texttt{4 defeats 5} & \texttt{5 defeats 4} \\ \hline \end{array} $$$$$$

In the example above, $$$r_1(1) = 0$$$, $$$r_1(2) = 1$$$, $$$r_1(3) = 3$$$, $$$r_1(4) = 3$$$, $$$r_1(5) = 3$$$, and $$$r_2(1) = 1$$$, $$$r_2(2) = 1$$$, $$$r_2(3) = 1$$$, $$$r_2(4) = 3$$$, $$$r_2(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$$$.

Input

Your program is to read from standard input. The input starts with a line containing an integer $$$n$$$, ($$$3 \leq n \leq 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.

Output

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.

ExamplesInput
5
1 0 2 0 1
Output
YES
Input
5
1 1 2 1 0
Output
NO

Source/Category

加入题单

算法标签：