# 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 edge1 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 ai knights.

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

### 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 ai, 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.

5
2
3
2
3
3

YES

3
2
2
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.

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

• For Subtask 1 (20 points), every knight wants to be in a squad of size 2 (that is, ai = 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, ai ≤ 3 for all i).
• For Subtask 3 (17 points), all the knights want to be in squads of the same size (that is, ai = aj 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.

Privacy statement