I'm trying to understand the solution to an algorithm/logic problem. The problem statement is as follows:
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. For 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. Help Vasya to permute integers in such a way that the number of positions in a new array, where integers are greater than in the original one, is maximal.
Input The first line contains a single integer 𝑛 (1≤𝑛≤105) — the length of the array. The second line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤109) — the elements of the array.
Output 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.
Sample I/O: example input/output
I've looked at the solution but couldn't really understand the intuition behind it. I understand how it works, but I don't understand WHY it works. Here's the solution:
The answer is 𝑛 minus maximal number of equal elements. Let the maximal number of equals be 𝑥. Let's prove that 𝑛−𝑥 is reachable. It's clear that for every permutation of the array the answer will be the same, so let's sort the array in non-decreasing order. Now we should just make a left shift on 𝑥. After it, the 𝑛−𝑥 right elements will move to a position of a smaller element. Now let's prove that the answer is no more than 𝑛−𝑥. Let's consider some permutation. It's known that every permutation breaks into cycles. Let's look at two occurrences of the same number in the same cycle. Then there is at least one number between them which will move on a position of a non-smaller element. Even if it the same occurrence and even if the length of the cycle is 1, we can say that for every occurrence of this number there is at least one number that moves on a position of a non-smaller one. So if some number occurs 𝑥 times, there are at least 𝑥 bad positions and therefore no more than 𝑛−𝑥 good positions.
Please break this explanation down to a level I can understand. I've tried tons of dry-runs but couldn't figure out the logic behind it. To me, this is black magic.