← 返回题目列表

Codeforces · 651/B

B. 美丽的画作

中文机器翻译题面 查看原题

新展览已交付 n 张图片。第i幅画有美女ai。我们知道,每次参观者从一幅画变成一幅更美丽的画时,他都会感到高兴。

我们可以按任何顺序排列图片。当访问者从第一张到最后一张传递所有图片时,最多可能有多少次会感到高兴?换句话说,我们可以以任何顺序重新排列 a 的元素。索引 i (1 ≤ i ≤ n - 1) 的最大可能数量是多少,使得 ai + 1 > ai。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 1000) — 绘画次数。

第二行包含序列 a1, a2, ..., an (1 ≤ ai ≤ 1000),其中 ai 表示第 i 幅画的美丽。

输出

打印一个整数——最优重排后相邻对的最大可能数量,使得 ai + 1 > ai。

示例

输入 #1

5
20 30 10 50 40

输出 #1

4

输入 #2

4
200 100 100 200

输出 #2

2

注意

在第一个示例中,最佳顺序为:10、20、30、40、50。

在第二个示例中,最佳顺序为:100、200、100、200。