{"raw_statement":[{"iden":"statement","content":"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. Help Vasya find the maximal number of such integers.\n\nFor instance, if we are given an array $[10, 20, 30, 40]$, we can permute it so that it becomes $[20, 40, 10, 30]$. Then on the first and the second positions the integers became larger ($20>10$, $40>20$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $2$. Read the note for the first example, there is one more demonstrative test case.\n\nHelp Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal."},{"iden":"input","content":"The first line contains a single integer $n$ ($1 \\leq n \\leq 10^5$) — the length of the array.\n\nThe second line contains $n$ integers $a_1, a_2, \\ldots, a_n$ ($1 \\leq a_i \\leq 10^9$) — the elements of the array."},{"iden":"output","content":"Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array."},{"iden":"examples","content":"Input\n\n7\n10 1 1 1 5 5 3\n\nOutput\n\n4\n\nInput\n\n5\n1 1 1 1 1\n\nOutput\n\n0"},{"iden":"note","content":"In the first sample, one of the best permutations is $[1, 5, 5, 3, 10, 1, 1]$. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.\n\nIn the second sample, there is no way to increase any element with a permutation, so the answer is 0."}],"translated_statement":[{"iden":"statement","content":"你被给定一个整数数组。Vasya 可以对其中的整数进行排列（改变顺序）。他希望这样做，使得尽可能多的整数出现在原本较小整数所在的位置。请帮助 Vasya 找到满足这一条件的最大整数个数。\n\n例如，给定数组 $[ 10, 20, 30, 40 ]$，我们可以将其排列为 $[ 20, 40, 10, 30 ]$。此时，在第一和第二个位置，整数变大了（$20 > 10$，$40 > 20$），而在第三和第四个位置没有变大，因此该排列中 Vasya 想要最大化的目标值为 $2$。请参阅第一个示例的注释，那里还有一个演示用例。\n\n请帮助 Vasya 对整数进行排列，使得新数组中比原数组对应位置元素更大的元素个数最大化。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 数组的长度。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 10^9$) —— 数组的元素。\n\n请输出一个整数 —— 在排列后，有多少个数组元素出现在原本有更小元素的位置上，且该数量最大。\n\n在第一个样例中，一个最优排列是 $[ 1, 5, 5, 3, 10, 1, 1 ]$。从第二个位置到第五个位置，元素都变大了，因此该排列的答案为 4。\n\n在第二个样例中，无法通过任何排列使任一元素变大，因此答案为 0。\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 数组的长度。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 10^9$) —— 数组的元素。"},{"iden":"output","content":"请输出一个整数 —— 在排列后，有多少个数组元素出现在原本有更小元素的位置上，且该数量最大。"},{"iden":"examples","content":"输入710 1 1 1 5 5 3输出4输入51 1 1 1 1输出0"},{"iden":"note","content":"在第一个样例中，一个最优排列是 $[ 1, 5, 5, 3, 10, 1, 1 ]$。从第二个位置到第五个位置，元素都变大了，因此该排列的答案为 4。在第二个样例中，无法通过任何排列使任一元素变大，因此答案为 0。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the original array of integers.  \nLet $ B = (b_1, b_2, \\dots, b_n) $ be a permutation of $ A $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ B $ is a permutation of $ A $, i.e., $ B \\in \\text{Perm}(A) $\n\n**Objective**  \nMaximize the number of indices $ i \\in \\{1, \\dots, n\\} $ such that $ b_i > a_i $.  \nThat is, compute:  \n$$\n\\max_{B \\in \\text{Perm}(A)} \\left| \\left\\{ i \\in \\{1, \\dots, n\\} \\mid b_i > a_i \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}