/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 700 点
問題文
N 匹の猫がいます。 猫には 1 から N まで番号が振られています。
各猫はある色の帽子を被っています。 猫 i は「自分を除く N-1 匹の猫が被っている帽子の色の種類数はちょうど a_i である」と言っています。
すべての猫の発言と矛盾しないような帽子の色の組合せが存在するか判定してください。
制約
- 2 ≤ N ≤ 10^5
- 1 ≤ a_i ≤ N-1
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
すべての猫の発言と矛盾しないような帽子の色の組合せが存在するならば、Yes を出力せよ。
存在しないならば、No を出力せよ。
入力例 1
3 1 2 2
出力例 1
Yes
例えば、猫 1, 2, 3 の帽子の色がそれぞれ赤、青、青ならば、すべての猫の発言と矛盾しません。
入力例 2
3 1 1 2
出力例 2
No
猫 1 の発言から、猫 2, 3 の帽子の色は同一です。 また、猫 2 の発言から、猫 1, 3 の帽子の色は同一です。 よって、猫 1, 2 の帽子の色は同一ですが、これは猫 3 の発言に矛盾します。
入力例 3
5 4 3 4 3 4
出力例 3
No
入力例 4
3 2 2 2
出力例 4
Yes
入力例 5
4 2 2 2 2
出力例 5
Yes
入力例 6
5 3 3 3 3 3
出力例 6
No
Score : 700 points
Problem Statement
There are N cats. We number them from 1 through N.
Each of the cats wears a hat. Cat i says: "there are exactly a_i different colors among the N - 1 hats worn by the cats except me."
Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.
Constraints
- 2 ≤ N ≤ 10^5
- 1 ≤ a_i ≤ N-1
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
Print Yes if there exists a sequence of colors of the hats that is consistent with the remarks of the cats; print No otherwise.
Sample Input 1
3 1 2 2
Sample Output 1
Yes
For example, if cat 1, 2 and 3 wears red, blue and blue hats, respectively, it is consistent with the remarks of the cats.
Sample Input 2
3 1 1 2
Sample Output 2
No
From the remark of cat 1, we can see that cat 2 and 3 wear hats of the same color. Also, from the remark of cat 2, we can see that cat 1 and 3 wear hats of the same color. Therefore, cat 1 and 2 wear hats of the same color, which contradicts the remark of cat 3.
Sample Input 3
5 4 3 4 3 4
Sample Output 3
No
Sample Input 4
3 2 2 2
Sample Output 4
Yes
Sample Input 5
4 2 2 2 2
Sample Output 5
Yes
Sample Input 6
5 3 3 3 3 3
Sample Output 6
No