AT_arc136_e [ARC136E] Non-coprime DAG

有一个包含 $N$ 个顶点的有向图 $G$，顶点编号为 $1$ 到 $N$。 对于任意两个顶点 $i, j$（$1 \leq i, j \leq N$，$i \neq j$），当且仅当同时满足以下两个条件时，存在一条从 $i$ 到 $j$ 的有向边 $i \to j$： - $i < j$ - $\mathrm{gcd}(i, j) > 1$ 此外，每个顶点都有一个确定的价值，顶点 $i$ 的价值为 $A_i$。 请你选择一个顶点集合 $s$，使其满足以下条件： - 对于 $s$ 中任意两个不同的顶点对 $(x, y)$（$x < y$），在图 $G$ 上都无法从 $x$ 到 $y$ 到达。 请你求出 $s$ 中所有顶点的价值之和的最大可能值。

输入通过标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

请输出答案。

### 限制条件 - $1 \leq N \leq 10^6$ - $1 \leq A_i \leq 10^9$ - 所有输入的值均为整数 ### 样例解释 1 可以选择 $s = \{1, 2, 3, 5\}$。 ### 样例解释 2 可以选择 $s = \{1, 5, 6\}$。 由 ChatGPT 4.1 翻译