{"problem":{"name":"A. Reorder the Array","description":{"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. ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1007A"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint 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.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n第一行包含一个整数 $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$) —— 数组的元素。\n\n## Output\n\n请输出一个整数 —— 在排列后，有多少个数组元素出现在原本更小元素的位置上，且该数值最大。\n\n[samples]\n\n## Note\n\n在第一个样例中，其中一个最优排列是 $[ 1, 5, 5, 3, 10, 1, 1 ]$。从第二位到第五位，元素变大了，因此该排列的答案为 4。在第二个样例中，无论如何排列都无法让任何元素变大，因此答案为 0。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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 $ \\sigma $ be a permutation of $ \\{1, 2, \\dots, n\\} $, defining a rearranged array $ B = (a_{\\sigma(1)}, a_{\\sigma(2)}, \\dots, a_{\\sigma(n)}) $.\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\\} $\n\n**Objective**  \nMaximize the number of indices $ i \\in \\{1, \\dots, n\\} $ such that:  \n$$\na_{\\sigma(i)} > a_i\n$$  \nThat is, find:  \n$$\n\\max_{\\sigma \\in S_n} \\left| \\left\\{ i \\in \\{1, \\dots, n\\} \\mid a_{\\sigma(i)} > a_i \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1007A","tags":["combinatorics","data structures","math","sortings","two pointers"],"sample_group":[["7\n10 1 1 1 5 5 3","4"],["5\n1 1 1 1 1","0"]],"created_at":"2026-03-03 11:00:39"}}