Inversion Value of a Permutation

First, kill the wrong assumption: this is not asking for a permutation with exactly $k$ inversion pairs. It asks for exactly $k$ subsegments that contain at least one inversion. One inversion can poison a bunch of subsegments, so direct inversion-count tricks are the wrong tool.

Flip the Count

There are exactly

$T = n(n-1)/2$

subsegments with length at least $2$, because choosing endpoints $(l,r)$ with $l<r$ defines one.

Instead of counting subsegments that contain an inversion, count subsegments that contain no inversion.

A subsegment has no inversion if and only if it is strictly increasing. Since all values are distinct, this is clean: if the segment is increasing, no pair is inverted; if it is not increasing, some adjacent pair drops, and that adjacent pair is already an inversion.

So if the desired inversion value is $k$, then the number of increasing subsegments of length at least $2$ must be

$keep = T-k$.

Increasing Runs

Now look at the permutation as maximal contiguous increasing runs.

Example:

3 1 4 2

has runs:

[3], [1 4], [2]

Only subsegments fully inside one run are inversion-free. Any subsegment crossing a run boundary contains a descent at that boundary, so it definitely contains an inversion.

If a run has length $x$, the number of length-at-least-2 subsegments inside it is

$x(x-1)/2$.

Therefore, if the run lengths are $a_1,a_2,...,a_m$, then

$keep = \sum_i a_i(a_i-1)/2$.

Also, of course,

$\sum_i a_i = n$.

So the whole problem becomes this much smaller problem:

Find positive integers $a_i$ summing to $n$ such that

$\sum_i a_i(a_i-1)/2 = T-k$.

If impossible, output 0.

DP for Run Lengths

Since $n \le 30$, $T \le 435$. Tiny. We can use DP.

Let $dp[used][sum]$ mean we can choose some run lengths whose total length is used and whose triangular contribution is sum.

Transition: choose the next run length len, where used + len <= n. It adds

$len(len-1)/2$

to the sum.

We store the chosen len as a parent pointer so we can reconstruct the run lengths if $dp[n][T-k]$ is reachable.

Building the Permutation

Suppose DP gives run lengths like:

$a_1,a_2,...,a_m$.

We need a permutation whose maximal increasing runs have exactly those lengths.

The easy construction:

• First run gets the largest remaining values, printed in increasing order.
• Second run gets the next largest remaining values, printed in increasing order.
• Continue like this.

For example, with $n=6$ and run lengths [2,4]:

• first run uses 5 6
• second run uses 1 2 3 4

Permutation:

5 6 1 2 3 4

Inside each block, values increase. Between blocks, the last value of the earlier block is larger than the first value of the next block, so there is a descent. That means the maximal increasing runs are exactly the blocks we asked for.

No hidden magic, just force the run structure and let the formula do the counting.

Correctness Proof

Consider any subsegment. It has no inversion if and only if all its values are strictly increasing in order. If it is not strictly increasing, then at some adjacent position inside the subsegment there is a descent, which is an inversion. So inversion-free subsegments are exactly increasing subsegments.

Now split a permutation into maximal increasing runs. Every subsegment fully inside one run is increasing, so a run of length $x$ contributes $x(x-1)/2$ inversion-free subsegments. Any subsegment crossing between two runs contains the descent at that boundary, so it is not inversion-free. Therefore the total number of inversion-free subsegments is exactly the sum of $x(x-1)/2$ over all run lengths.

The DP considers every possible sequence of positive run lengths summing to at most $n$, tracking exactly this sum of triangular contributions. Thus, if it reaches state $(n,T-k)$, the reconstructed lengths describe a valid run structure with exactly $T-k$ inversion-free subsegments. If it cannot reach that state, no permutation can work, because every valid permutation would produce such a list of run lengths.

Finally, the construction realizes the chosen run lengths exactly: each block is internally increasing, and every earlier block uses larger numbers than every later block, so every boundary between blocks is a descent. Hence the maximal increasing runs are exactly the chosen blocks. The inversion value is therefore

$T-(T-k)=k$.

So the algorithm is correct.

Complexity

The DP has at most $31 \cdot 436$ states and tries at most $30$ run lengths per state. This is tiny. Per test case, the complexity is $O(n^2T)$, easily within limits.