\(P_i=\max(P_1,P_2,\ldots,P_i)\) が成り立つ要素を高い要素，そうでない要素を高くない要素と呼びます．

\(P\) が与えられたとき，\(f(P)\) を高速に計算する方法を考えます．

ある \(P\) に対して，\(x\) が高い値であるような \(x\) 全てに対する \(2^{ x-1}\) の総和を \(S\) と呼ぶことにします．

操作を行って \(k\) を先頭に持っていくとき，\(k\) は高い要素になり，高い要素でなくなる可能性があるのは \(1,2,\ldots,k-1\) なので，\(S\) の増加分は \(2^{k-1}\) であり，\(S\) の減少分は \(\sum_{i=1}^{k-1}2^{i-1} < 2^{k-1}\) なので必ず \(S\) は \(1\) 以上増加します．

また，高くない要素のうち最小のものを選んで操作を行えば \(S\) を一回の操作でちょうど \(1\) 増やすことができます．

以上の議論より，\(f(P)= 2^{N}-1-S\) が成立します．

もとの問題に戻ると，ありうる順列全てに対する \(S\) の総和が分かればよいです．これは各 \(x\) 毎に独立に考えられ，\(x\) が高い値となるような順列の個数も \(\mathrm{O}(1)\) で求められるので全体で \(\mathrm{O}(N)\) で解くことができます．

原案：nok0