AtCoder Grand Contest 016

B - Colorful Hats


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

Submit提出する