← 返回题目列表

Codeforces · 1025/D

D. 恢复 BST

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

仓鼠迪玛喜欢啃不同的东西:笼子、棍子、糟糕的问题解决者,甚至树木!

最近他发现了一棵二叉搜索树,并本能地蚕食了它的所有边,从而弄乱了顶点。迪马知道,如果安德鲁已经彻底组装了这棵树很长时间,回到家看到他的创作被拆除,他会非常沮丧。

为了不让这种情况发生,Dima 必须恢复二叉搜索树。幸运的是,他注意到由直接边连接的任何两个顶点的最大公约数值都超过 $$$1$$$。

帮助Dima构建这样的二叉搜索树或确定这是不可能的。二叉搜索树的定义和属性可以在这里找到。

输入

第一行包含顶点数 $$$n$$$ ($$$2 \le n \le 700$$$)。

第二行包含 $$$n$$$ 不同的整数 $$$a_i$$$ ($$$2 \le a_i \le 10^9$$$) — 按升序排列的顶点值。

输出

如果可以重新组装二叉搜索树,使得边连接的任意两个顶点的最大公约数大于 $$$1$$$,则打印“Yes”(为清楚起见,加引号)。

否则,打印“No”(为了清楚起见,加引号)。

示例

输入 #1

6
3 6 9 18 36 108

输出 #1

Yes

输入 #2

2
7 17

输出 #2

No

输入 #3

9
4 8 10 12 15 18 33 44 81

输出 #3

Yes

注意

下图展示了第一个示例的可能树之一。

下图展示了第三个示例的可能树之一。