バブルソートの要領で数列をソートすることを考えると、順序が逆転している値の組に対してちょうど \(1\) 回操作をし、逆転していない組に対して操作をすることなくソートができます。

逆に、どのような順序で操作を行っても、操作により直接順序を入れ替えない限り、\(2\) つの要素の位置関係は変化しません。
つまり \(i < j\) かつ \(P_i > P_j\) であるような \(i,j\) が存在したとき、この \(2\) つの値を正しい順序にするためには直接入れ替える必要があります。

よって求めるべきものは、\(i < j\) かつ \(P_i > P_j\) であるような \(i,j\) 全てについての \(P_i+P_j\) の和です。

\(i\) を固定して、\(j\) に関しての和を取ることを考えます。\(i < j\) かつ \(P_i > P_j\) であるような \(j\) の、個数と \(P_j\) の和がわかればよく、これはセグメントツリーやfenwick treeを用いて求めることができます。

計算量は \(O(N\log N)\) になります。

実装例(C++)