样例文件

题目描述

现在需要你制作若干条项链。

给你 n 盒珠子，第 i 个盒子中有 $a_i$ 颗珠子。同一个盒子中的珠子颜色都是相同的，不同盒子的珠子颜色则不同。

每条项链要求恰好包含 n-1 颗珠子，且任意两颗珠子的颜色不同。

你希望用现有的珠子制作尽可能多条项链。

问：你最多能制作多少条项链？

输入

第一行：一个整数 n；

第二行：n 个整数 $a_i$。

输出

一个整数，表示答案。

样例1输入

4
1 2 3 4

样例1输出

3

样例1解释

样例中，最多可以制作 3 条项链，如下所示是一种可能的制作方案，每一行表示一条项链用到的珠子所在的盒子编号：

• 1, 3, 4
• 2, 3, 4
• 2, 3, 4

样例2输入

4
0 1 0 2

样例2输出

0

数据范围

$40\%$ 的数据，$2 ≤ n ≤ 5$，$0 ≤ a_i ≤ 300$。

$60\%$ 的数据，$2 ≤ n ≤ 15$，$0 ≤ a_i ≤ 10^6$。

$100\%$ 的数据，$2 ≤ n ≤ 55$，$0 ≤ a_i ≤ 5 × 10^8$。