题目描述

给定长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。

问是否存在一棵 $n$ 个结点，结点编号 $1 \sim n$ 的有根树使得：

• 设 $\operatorname{LCA}(p,q)$ 为结点 $p,q$ 的最近公共祖先编号。则对于所有 $1 \le i,j \le n$，有 $\operatorname{lcm}(a_i,a_j) \mid a_{\operatorname{LCA}(i,j)}$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行一个字符串 $\texttt{Yes}$ 或 $\texttt{No}$，分别表示存在和不存在。

样例

3
1 2 2

Yes

3
1 2 3

No

说明/提示

对于 $100\%$ 的数据：

• $1 \le n \le 10^5$；
• $1 \le a_i \le 10^9$。

本题开启捆绑测试。

• Subtask #1（$10 \ \text{pts}$）：$n \le 5$。
• Subtask #2（$20 \ \text{pts}$）：$a_i \le 4$。
• Subtask #3（$70 \ \text{pts}$）：无特殊限制。