Partial Sorting solution codeforces

Partial Sorting solution codeforces – Consider a permutation $^{†}$ $p$ of length $3 n$ . Each time you can do one of the following operations:

Sort the first $2 n$ elements in increasing order.
Sort the last $2 n$ elements in increasing order.

Partial Sorting solution codeforces

We can show that every permutation can be made sorted in increasing order using only these operations. Let’s call $f (p)$ the minimum number of these operations needed to make the permutation $p$ sorted in increasing order.

Given $n$ , find the sum of $f (p)$ over all $(3 n)!$ permutations $p$ of size $3 n$ .

Since the answer could be very large, output it modulo a prime $M$ .

$^{†}$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2, 3, 1, 5, 4]$ is a permutation, but $[1, 2, 2]$ is not a permutation ( $2$ appears twice in the array), and $[1, 3, 4]$ is also not a permutation ( $n = 3$ but there is $4$ in the array).