← 返回题目列表

Codeforces · 566/F

F. 可分图中的派系

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

正如你必须知道的,任意图中的最大派系问题是 NP 困难的。然而,对于某些特定类型的图,它可以有效地解决。

为了以防万一,让我们提醒您,无向图中的团是图的顶点的子集,使得该子集的任意两个顶点通过边连接。特别是,空顶点集和由单个顶点组成的集合是团。

让我们定义一组正整数 A = {a1, a2, ..., an} 的整除图,如下所示。给定图的顶点是集合 A 中的数字,并且两个数字 ai 和 aj (i ≠ j) 通过边连接当且仅当 ai 可被 aj 整除,或者 aj 可被 ai 整除。

给定一组非负整数 A。确定集合 A 的整除图中最大集团的大小。

输入

第一行包含整数 n (1 ≤ n ≤ 106),用于设置集合 A 的大小。

第二行包含 n 个不同的正整数 a1, a2, ..., an (1 ≤ ai ≤ 106) — 子集 A 的元素。该行中的数字按升序排列。

输出

打印单个数字 — 集合 A 的整除图中派系的最大大小。

示例

输入 #1

8
3 4 6 8 10 18 21 24

输出 #1

3

注意

在第一个样本测试中,大小为 3 的团例如是顶点 {3, 6, 18} 的子集。该图中不存在较大规模的派系。