正如你必须知道的,任意图中的最大派系问题是 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} 的子集。该图中不存在较大规模的派系。