题目描述

小美穿越到平行时空中，在她面前有 n 个石头和一个跷跷板。每个石头都有自己独特的重量。此外，小美的手中还持有无限多的魔法棒棒糖。每当她吃下一根魔法棒棒糖，她就能将 n 个石头中的一个石头的重量更改为其他 n−1 个石头中的一个石头的重量。 小美需要确保在吃下一些魔法棒棒糖后，能够从 n 个石头中任意挑选三个石头，并将它们任意分成两组：一组包含 1 个石头，另一组包含 2 个石头。 都能保证，当这两组石头分别放在跷跷板的两边时，只有包含 1 个石头的那一边会翘起来。 现在，小美需要计算出她最少需要吃下多少根魔法棒棒糖，以满足上述条件。

输入格式

第一行输入一个整数 n，表示石头的个数。 第二行输入 n 个正整数，代表每个石头的重量。

输出格式

输出一个整数，表示小美最少需要吃下多少根魔法棒棒糖才能满足要求。

样例输入/输出

5
2 2 2 2 2

0

7
1 2 3 4 5 6 7

3

样例解释

样例解释1

不用吃下任何一根魔法棒棒糖，就能满足题目的要求，因为所有石头的重量相同，无论怎么分组都能满足条件。

样例解释2

小美可以吃下 3 根魔法棒棒糖，将第一个石头的重量改成 4，第二个石头的重量改成 4，第七个石头的重量改成 5。这样，7 个石头的重量就变为 4, 4, 3, 4, 5, 6, 5，能够满足题目要求。

数据规模与提示

• 对于 10% 的数据保证：每个石头的重量都相同。
• 对于 20% 的数据保证：输入的每个石头重量都是递增的，并且增长幅度为 1。
• 对于100%保证：10≤n≤200000，1≤ai≤1000000000，其中 ai 表示第 i 个石头

时间限制：1000ms.

内存限制：256MB.

Source