Problem: Castle Cavalry

Want to try solving this problem? You can submit your code online if you log in or register.

Castle Cavalry

Input File: cavalryin.txt
Output File: cavalryout.txt
Time Limit: 1 second
Memory Limit: 1 GB

As the Queen's chief technologist, you have been tasked with organising the army's newest cutting edge¹ division: the cavalry.

Naturally, the Queen is sceptical, so to prove it's worth it you are going to conduct a quick field test. Firstly, you will need to group your knights into squads.

Unfortunately, the N knights in your division are very inexperienced, having only been training for two weeks! The ith knight (counting from 1) has told you that they would only be comfortable in a squad containing exactly a_i knights.

You can make as many or as few squads as you like of any size, so long as every knight is comfortable.

After feeding your whining, whinnying horses their pheasant-based supper, you return to your lonely lodge to determine if it is possible to divide up your cavalry.

Input

The first line of input will contain N, the number of knights in your division.

Then, N lines will follow. The ith line (counting from 1) will contain a_i, the size of the squad the ith knight wants to join.

Output

Print YES on a single line if it is possible to put the knights into squads such that they are all comfortable. If it is not possible, then print NO instead.

Sample Input 1

Sample Output 1

YES

Sample Input 2

Sample Output 2

NO

Explanation

In the first case, you can put knights 1 and 3 in one squad, and knights 2, 4 and 5 into a second one. This makes them all comfortable, so the answer is YES.

In the second case, you can put knights 1 and 2 together in the same squad, but then knight 3 cannot form a squad by themselves (since knight 3 wants to be in a squad of size 2). No matter what you do, one of the knights is going to get left out, so the answer is NO.

Subtasks & Constraints

For all subtasks, 1 ≤ N ≤ 100,000, and 1 ≤ a_i ≤ N.

For Subtask 1 (20 points), every knight wants to be in a squad of size 2 (that is, a_i = 2 for all i).
For Subtask 2 (15 points), each knight wants to be in a squad of size at most 3. However different knights might want to be in squads of different sizes (that is, a_i ≤ 3 for all i).
For Subtask 3 (17 points), all the knights want to be in squads of the same size (that is, a_i = a_j for all i and j).
For Subtask 4 (28 points), there are at most 1000 knights (that is, N ≤ 1000).
For Subtask 5 (20 points), no further constraints apply.