408531: GYM103181 L Hard work

Bob finally found a new home - with exactly $$$N$$$ rooms, all of them in a line - and he is extremely excited!

Now, the last thing he needs to do in order to be fully happy with his purchase is to paint all of the rooms in several colours. Although it would normally be hard work, Bob has a machine and $$$N$$$ paint buckets containing those colours. Naturally, he knows what colour each of the rooms should have. Therefore, every room will require a colour $$$c_{i}$$$ ($$$1 \leq c_{i} \leq K$$$).

Note that multiple rooms can have the same colour, but they will require different buckets. Moreover, Bob has a bucket for every room - meaning that if there are two rooms with colour number 2, he will have two buckets of that colour. This way, it is sure that he will get to his desired colour plan.

Bob starts at whatever room he desires and charges the machine with a colour. However, he is so excited that he cannot even think about what he must pick - indeed, Bob charges the machine with a random bucket. Therefore, two things can happen: Bob either picks the correct colour to charge the machine with, or he does not. If he does, he can paint the room and move to a room of his liking that was not painted yet. If he does not, he has to recharge the machine with another random bucket, up until he gets it right. Note that he always puts back the buckets that he has not used, since Bob will need it later on.

Since Bob always picks the bucket to charge the machine with at random, what is the expected amount of times he will have to charge it if he wants to paint all of the rooms? Bear in mind that Bob always chooses the first (and following) rooms optimally. That is to say, he will always pick a room in a way such that the expected number of total recharges over all rooms is minimized.

Please note that if there are $$$K$$$ buckets left in the machine, each of them has a probability of $$$\frac{1}{K}$$$ to be picked. Hence if there are $$$Q$$$ buckets of colour $$$3$$$, for instance, the probability of picking a bucket with that colour is $$$\frac{Q}{K}$$$.

The first line of input contains two integers: $$$N$$$ ($$$1\leq N \leq 10^5$$$) and $$$K$$$ ($$$1\leq K \leq N$$$), denoting the number of rooms and the number of different colours.

The second line shall contain $$$N$$$ integers, $$$c_i$$$ ($$$1 \leq i \leq N$$$ and $$$1 \leq c_i \leq K$$$), denoting the colour that room $$$i$$$ must be painted with.

Print an integer $$$X$$$ denoting the number of times Bob is expected to charge the machine, knowing that he picks the bucket randomly every single time and that he chooses the order of the rooms such that the final result will be minimized. Print X at a precision of $$$10^{-6}$$$.

6 3
2 1 3 3 2 3

12.50000000