Logan is cleaning his apartment. In particular, he must sort his old favorite sequence, , of positive integers in nondecreasing order. He's tired from a long day, so he invented an easy way (in his opinion) to do this job. His algorithm can be described by the following pseudocode:
while isNotSorted(P) do {
WaitOneMinute();
RandomShuffle(P)
}
Can you determine the expected number of minutes that Logan will spend waiting for to be sorted?
Input Format
The first line contains a single integer, , denoting the size of permutation .
The second line contains space-separated integers describing the respective elements in the sequence's current order, .
Constraints
Output Format
Print the expected number of minutes Logan must wait for to be sorted, correct to decimal places.
Sample Input
2
5 2
Sample Output
2.000000
Explanation
There are two permutations possible after a random shuffle, and each of them has probability . The probability to get the sequence sorted after the first minute is . The probability that will be sorted after the second minute is , the probability will be sorted after the third minute is , and so on. So, the answer is equal to the following sum: