Vlad and Candies II

Problem Description

Not long ago, Vlad celebrated his birthday and received a package of candies. There are $n$ types of candies, and the $i$-th type has $a_i$ pieces ($1 \le i \le n$).

Vlad decides to eat only one candy at a time. To get the most pleasure out of eating, Vlad does not want to eat two candies of the same type consecutively.

Help him figure out whether he can eat all the candies without ever eating two of the same type consecutively.

In short, given $n$ positive integers $a_i$, where $a_i$ means there are $a_i$ copies of value $i$, determine whether there exists a sequence that uses all the numbers with no two equal values adjacent.

Input Format

The first line contains an integer $n$.

The second line contains $n$ positive integers.

Output Format

Output one line: if such a sequence exists, output YES; otherwise output NO.

Sample Input

2
1 1

Sample Output

YES

Sample Explanation

There are only two cases:

1 2

2 1

No matter which candy is eaten first, all candies can be finished without eating the same type consecutively.

Constraints

For $100\%$ of the data, $1 \leq n \leq 5\,000\,000$, $1 \leq a_i \leq 2^{30}$.