分蛋糕

题目描述

小珅有 n 种蛋糕，编号为 1～n，第 i 种蛋糕有 $a_i$ 个。

小珅现在希望把这些蛋糕尽可能多地分成若干相同的组，作为给其他小伙伴的礼品。“相同”指的是每一组蛋糕都包含相同数量的不同种类的蛋糕，且最终不能有蛋糕剩下。注意，不能把一个蛋糕分成多份。

例如：小珅有 3 种蛋糕，1 号蛋糕有 4 个，2 号蛋糕有 6 个，3 号蛋糕有 18 个。那么小珅最多就只能分出 2 组相同的礼品，每组礼品包含 2 个 1 号蛋糕、3 个 2 号蛋糕、9 个 3 号蛋糕。

但小珅现在希望能分出更多组礼品来，又同时要保证每组蛋糕相同。于是他决定做这样一件事情：小珅将挑出若干种类的蛋糕，让这些特定种类的蛋糕不再作为礼品，也相当于把它们去掉。

比如：小珅有 3 种蛋糕，1 号蛋糕有 4 个，2 号蛋糕有 6 个，3 号蛋糕有 18 个。小珅如果选择让 1 号蛋糕不再作为礼品，那么他就最多可以分出 3 组相同的蛋糕，每组包含 2 个 2 号蛋糕和 6 个 3 号蛋糕。

现在小珅想要知道，他最少要选出几种蛋糕让它们不再是礼品，才能使得比刚开始分出的组数更多。你需要输出这个最小值。

假如小珅无论如何都没有办法做到分出更多组相同蛋糕的话，输出不去掉任何蛋糕的情况下最多能够分出多少组相同的蛋糕。

注意：

1. 刚开始能够分出的组数有可能为 0。
2. 让所有种类的蛋糕都不作为礼物的话，最后相当于只能分 0 组。

输入描述

第一行一个正整数 n，表示有 n 种蛋糕。

接下来一行共 n 个用空格分隔的正整数 $a_i$，表示第 i 种蛋糕的数量。

输出描述

一行。如果小珅无法让分出的组数变多，输出一个正整数，表示最多能够分出多少组相同的蛋糕；否则输出一个正整数，表示最少要选出几种蛋糕不再作为礼物。

样例 1

输入：

3
2 2 2

输出：

2

样例 1 解释：把所有蛋糕都分完，最多分出两组相同的蛋糕。同时容易发现，不论把哪些种类的蛋糕去掉，都没有办法分出大于两组的相同蛋糕。

样例 2

输入：

4
4 4 6 18

输出：

2

样例 2 解释：把所有蛋糕都分完，最多分出两组相同的蛋糕。但是如果把第一种和第二种蛋糕去掉，就可以分出 3 组相同的蛋糕；或者把第三种和第四种蛋糕去掉，就可以分出 4 组相同的蛋糕。但不论如何，要分出更多组相同蛋糕至少需要去掉两种不同的蛋糕。

输入样例 #3

2
1 1

输出样例 #3

1

数据范围

• 对于 20% 的数据，所有 $a_i$ 均为 2 的幂次，即 $a_i$ = 2^x，x 为非负整数。
• 对于 50% 的数据，所有 $a_i$ 均满足 $a_i$ = 2^x×3^y，x、y 为非负整数。
• 有额外的 10% 的数据，保证不论如何选择要被去掉的蛋糕种类，都无法分出更多的组相同蛋糕。
• 对于 100% 的数据，2 ≤ n ≤ 10^5，1 ≤ $a_i$ ≤ 3^13。（有一些数据的 n 相对比较小。）