← 返回题目列表

Codeforces · 429/C

C. 猜树

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

Iahub 和 Iahubina 去树木茂盛的森林里野餐。不到 5 分钟后,Iahub 就想起了编程中的树。而且,他发明了一个新问题,Iahubina必须解决它,否则Iahub不会给她食物。

Iahub 问 Iahubina:你能建立一棵有根树,这样

- 每个内部节点(至少有一个儿子的节点)至少有两个儿子;
- 节点 i 在其子树中有 ci 节点?

Iahubina 必须猜测这棵树。作为一个聪明的女孩,她意识到可能没有一棵树可以遵循 Iahub 的限制。这样,Iahub就会吃掉所有的食物。您需要帮助 Iahubina:确定是否至少有一棵树遵循 Iahub 的限制。所需的树必须包含 n 个节点。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 24)。下一行包含 n 个正整数:第 i 个数字表示 ci (1 ≤ ci ≤ n)。

输出

如果存在至少一棵遵循 Iahub 限制的树,则在第一行输出“YES”(不带引号),否则输出“NO”(不带引号)。

示例

输入 #1

4
1 1 1 4

输出 #1

YES

输入 #2

5
1 1 5 2 1

输出 #2

NO