Let us rephrase the problem. The final sequence can be thought of as the sequence \(B\) generated by the following procedure:

• Consider a multiset \([a_1, a_2, \dots, a_K]\) of size \(K\) and an empty array \(B\). Perform the following operation for \(i = 1, 2, \dots, N - K\):

  • Pick a random element from the multiset and append it to the end of \(B\).
  • Insert \(a_{i + K}\) to the multiset.

• Finally, randomly shuffle the remaining \(K\) elements of the multiset and append them to the end of \(B\).

Let \(f(i) = \max(i - K, 0)\). \(a_i\) is inserted to the multiset in the \(f(i)\)-th operation.

For a pair \((i, j)(i < j)\) of indices, let us find the probability that \(a_i\) and \(a_j\) are swapped in the final array.

If there exists an instant when \(a_i\) and \(a_j\) are in the multiset at the same time, it follows from the nature of the operation that the probability that \(a_i\) comes before \(a_j\) in the final array is exactly \(1/2\). Furthermore, the probability of the two elements existing in the multiset at the same time is \(p^{f(j) - f(i)}\) where \(p = (K - 1) / K\). Therefore, \(a_i\) and \(a_j\) are swapped with probability \({p^{f(j) - f(i)}} / {2}\).

After simplifying the expressions, we now see that the essence of this problem is:

• finding the sum of \(p^{f(j) - f(i)} = {p^{f(j)}} / {p^{f(i)}}\) for all pairs \((i, j)\) of indices that satisfy \(i < j\) and \(a_i > a_j\).

If we fix \(j\), this is equivalent to finding the sum of \({1} / {p^{f(i)}}\) for all \(i\) that satisfy \(i < j\) and \(a_i > a_j\). It can be found by a Fenwick tree just like in the computation of inversion numbers.