The following holds for \(f(P)\).

Let \(L_{P_{i}}\) be the number of \(j\) satisfying \(j < i\) and \(P_{j} < P_{i}\). Let \(R_{P_{j}}\) be the number of \(j\) satisfying \(i > j\) and \(P_{j} < P_{i}\). Then, \(f(P) = \sum_{i = 1}^{N} \min(L_{i}, R_{i})\).

This can be shown from the fact that whether \(A_{i} < A_{j}\) holds depends only on the sign of \(A_{j}\) if \(P_{i} < P_{j}\), and only on the sign of \(A_{i}\) if \(P_{i} > P_{j}\).

Let \(X[i][j]\) be the sum of \(\min(L_{j}, R_{j})\) over all \(P\) satisfying \(P_{K} = i\).

Then, the answer can be expressed as \(\sum X[a][j]\).

We want to find all \(X[a][j]\).

When \(a > j\)

For any integer \(b\) with \(0 \leq b < j\), the following holds:

• The number of permutations \(P\) satisfying \(L_{j} = b\) and \(P_{K} = a\) is \(\dfrac{(N - 1)!}{j}\)

Therefore, \(X[a][j] = \displaystyle\dfrac{(N - 1)!}{j}\sum_{b = 0}^{j - 1}\min(b, j - 1 - b)\). This value can be computed in \(O(1)\) if factorials and inverses are precomputed.

When \(a = j\)

When \(L_{j}, R_{j}\) are fixed, the number of \(P\) can be expressed by the following formula:

\[\binom{K - 1}{L}\cdot \binom{N - K}{R}\cdot(j - 1)!\cdot(N - j)!\]

Therefore, it suffices to find the sum of \(\binom{K - 1}{L}\cdot \binom{N - K}{R}\cdot\min(L, R)\) over all \(L, R\).

Computing naively allows us to find \(X[j][j]\) in \(O(j)\) time, but finding \(X[j][j]\) naively for all \(j\) results in TLE, so we compute \(X[j][j]\) for all \(j\) simultaneously using convolution.

Let \(Y_{j}\) be the sum of \(\binom{K - 1}{L}\cdot \binom{N - K}{R}\cdot\min(L, R)\) over integers \(L, R\) satisfying \(L< R\) and \(L + R + 1 = j\).

Define polynomials \(f(x), g(x)\) such that the following hold:

• \([x^{l}]f(x) = \binom{K - 1}{l}\cdot l\)
• \([x^{r}]g(x) = \binom{N - K}{r}\)

Then, the following formula holds for \(Y_{j}\):

\[Y_{j} = \sum_{L + R = j - 1, L < R}[x^{l}]f(x)\cdot[x^{r}]g(x)\]

Without the condition \(L < R\), we can find \(Y_{j}\) for any \(j\) with one convolution.

Even with the condition \(L < R\), using divide-and-conquer and convolution, we can compute it in time complexity \(O(N\log^{2}(N))\).

This gives us the contribution to \(X[j][j]\) for the case \(L < R\). The case \(L\geq R\) can be handled similarly.

When \(a < j\)

With similar reasoning to when \(a > j\), we have \(\displaystyle\sum_{k = 1}^{N}X[k][j] = \dfrac{N!}{j}\sum_{b = 0}^{j - 1}\min(b, j - 1 - b)\).

Also, since the value does not change for any \(X[k][j]\) satisfying \(k < j\) nor for any \(X[k][j]\) satisfying \(k > j\), and the value of \(X[j][j]\) has been computed above, \(X[a][j]\) can be computed in \(O(1)\).

We have found \(X[i][j]\) for any \(i, j\), so the original problem can also be answered by appropriately updating differences.

Specifically, after finding \(\sum X[1][j]\) based on the above information, using the fact that \(\sum X[a + 1][j] - \sum X[a][j] = X[a + 1][a + 1] - X[a][a] + X[a + 1][a] - X[a][a + 1]\), we can find \(\sum X[a][j]\) in the order \(a = 2, 3, \dots, N\).

The bottleneck is the part of finding \(X[a][j]\) when \(a = j\), and the time complexity is \(O(N\log^{2}{N})\).