← 返回题目列表

AtCoder · agc016_b

B. 彩色帽子

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

有 N 猫。 我们对它们进行编号 1 通过 N.

每只猫都戴着帽子。 猫 i 说:“正好有 a_i 不同颜色之间 N - 1 除了我之外其他猫都戴的帽子。”

判断是否存在与猫的评论一致的帽子颜色序列。

约束

  • 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