E. Election
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Xiangtan University is gearing up for an election to choose its student union president. The candidates are Donald Trump and Joe Biden. The university is divided into $$$n$$$ electoral constituencies. The i-th constituency possesses $$$a_i$$$ votes. In this electoral system, the candidate who secures the majority in a constituency seizes all the votes from that particular constituency.

As a student at Xiangtan University, Clamee has been provided with the information regarding the number of votes in each constituency. He is curious to know whether any legal difference in the number of votes can definitively determine the result in each electoral constituency without ambiguity. In other words, she wants to understand if the vote count differences are sufficient to ensure a unique election outcome in every single constituency.

Input

The initial line of the input provides a single integer $$$n~(1\le n \le 10^5)$$$, indicating the total number of electoral constituencies.

The following line lists $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n~(1 \le a_i,~\sum{a_i} \le 2^{31}-1, )$$$, each representing the vote count for the ith electoral constituency.

Output

For each test case, output "YES" (without quotes) if all legal difference in the number of votes can uniquely determine the outcome of each electoral constituency, and "NO" (without quotes) otherwise.

Examples
Input
4
1 2 3 4
Output
NO
Input
4
114 515 1919 810
Output
YES
Note

In the first test case, $$$+1+2-3+4=-1-2+3+4=4$$$, so the answer is "NO".

In the second test case, all legal difference in the number of votes can uniquely determine the outcome of each electoral constituency, so the answer is "YES".