← 返回题目列表

Codeforces · 1007/A

A. 重新排列数组

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

You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand.帮助 Vasya 找到此类整数的最大数量。

例如,如果给定一个数组 $$$[10, 20, 30, 40]$$$,我们可以对其进行排列,使其变为 $$$[20, 40, 10, 30]$$$。然后,在第一个和第二个位置上,整数变得更大($$$20>10$$$,$$$40>20$$$),而在第三个和第四个位置上则没有,因此对于这个排列,Vasya 想要最大化的数字等于 $$$2$$$。 Read the note for the first example, there is one more demonstrative test case.

帮助 Vasya 排列整数,使新数组中整数大于原始数组的位置数最大。

输入

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array.

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组的元素。

输出

打印单个整数 - 排列后位于初始数组中较小元素所在位置的数组元素的最大数量。

示例

输入 #1

7
10 1 1 1 5 5 3

输出 #1

4

输入 #2

5
1 1 1 1 1

输出 #2

0

注意

In the first sample, one of the best permutations is $$$[1, 5, 5, 3, 10, 1, 1]$$$.从第二到第五的位置,元素变得更大,所以这个排列的答案是 4。

在第二个示例中,无法通过排列来增加任何元素,因此答案为 0。