CF1768E Partial Sorting

Consider a permutation $ ^\dagger $ $ p $ of length $ 3n $ . Each time you can do one of the following operations: - Sort the first $ 2n $ elements in increasing order. - Sort the last $ 2n $ elements in increasing order. 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 $ (3n)! $ permutations $ p $ of size $ 3n $ . Since the answer could be very large, output it modulo a prime $ M $ . $ ^\dagger $ 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).

N/A

N/A

In the first test case, all the permutations are: - $ [1, 2, 3] $ , which requires $ 0 $ operations; - $ [1, 3, 2] $ , which requires $ 1 $ operation; - $ [2, 1, 3] $ , which requires $ 1 $ operation; - $ [2, 3, 1] $ , which requires $ 2 $ operations; - $ [3, 1, 2] $ , which requires $ 2 $ operations; - $ [3, 2, 1] $ , which requires $ 3 $ operations. Therefore, the answer is $ 0+1+1+2+2+3=9 $ .