You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

建水紫陶的规格挑选

题目背景

建水紫陶是云南独有的传统名陶。紫陶大师小李最近烧制了一批共 $n$ 个紫陶罐。为了参加展览，他希望能从中挑出一套“紫陶套罐”组合。

题目描述

这 $n$ 个紫陶罐的大小规格分别为 $a_1, a_2, \dots, a_n$。 小李对“紫陶套罐”的审美要求极高。他认为，被挑出来的这一套紫陶罐，必须要满足：集合中任意两个不同的陶罐，要么较小的规格能整除较大的规格，要么较大的规格能整除较小的规格。（例如：规格为 2、4、8 的三个罐子可以组成套罐，因为 2 能整除 4 和 8，4 能整除 8）。

小李希望选出的“紫陶套罐”包含的罐子数量尽可能多。如果有多个相同规格的罐子，可以把它们全部选入套罐中（自己整除自己也是合法的）。 请你帮小李算一算，为了得到包含最多罐子的“紫陶套罐”，他最少需要扔掉几个不符合要求的紫陶罐？

输入格式

第一行包含一个正整数 $n$，表示紫陶罐的总数。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，依次表示每个紫陶罐的规格大小。相邻整数之间用空格隔开。

输出格式

输出一个整数，表示最少需要扔掉的紫陶罐数量。

样例 #1

样例输入 #1

6
2 4 8 3 9 6

样例输出 #1

3

样例 #2

样例输入 #2

5
1 1 1 1 1

样例输出 #2

0

提示与数据范围

【样例解释 1】 原序列可以挑选出的最大合法子集为 {2, 4, 8}，包含了 3 个紫陶罐。 也可以挑选 {3, 6} 或 {3, 9}，但数量只有 2 个，不是最优解。 最优方案是保留 {2, 4, 8}，扔掉剩余的 3 个罐子。故输出 3。

【样例解释 2】 所有罐子规格都是 1，1 能够整除 1，全部保留，不需要扔掉任何罐子。

【数据范围】 对于 $30\%$ 的数据，满足 $1 \le n \le 1000$。 对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^6$。