We call an element satisfying \(P_i=\max(P_1,P_2,\ldots,P_i)\) a high element, and an element that does not satisfy this a non-high element.

Let us consider how to compute \(f(P)\) efficiently for a given \(P\).

For a given \(P\), let \(S\) be the sum of \(2^{x-1}\) over all \(x\) that are high values.

When we perform the operation of moving \(k\) to the front, \(k\) becomes a high element, and the elements that may cease to be high are \(1,2,\ldots,k-1\). Thus, the increase in \(S\) is \(2^{k-1}\), and the decrease in \(S\) is \(\sum_{i=1}^{k-1}2^{i-1} < 2^{k-1}\), so \(S\) always increases by at least \(1\).

Moreover, by choosing the smallest non-high element and performing the operation, \(S\) can be increased by exactly \(1\) in one operation.

From the above argument, \(f(P)= 2^{N}-1-S\).

Returning to the original problem, it suffices to find the sum of \(S\) over all possible permutations. This can be considered independently for each \(x\), and the number of permutations for which \(x\) is a high value can also be computed in \(\mathrm{O}(1)\), so the whole problem can be solved in \(\mathrm{O}(N)\).

Proposed by: nok0