以下では、順列が左右一列に並んでいるものとし、添字が小さい側を左側、添字が大きい側を右側とよぶことにします。
また、操作中の順列と区別するため、最初の時点における（入力で与えられる） \(P_i\) を \(P^0_i\) と書くことにします。

\(P\) をソートするために必要なコストの総和を最小値を下から評価することを考えます。
\(P\) をソートするために必要なコストの総和は、\(P\) の各要素についての「その要素を左に動かす（\(=1\) つ左の要素と交換する）ような操作についてのコストの総和」の和として計算する事ができます。
ここで、\(1\leq i\leq N\) に対して、\(A_i\) を次の条件をみたす整数 \(j\) の個数として定義します。

• \(1\leq j\leq i-1\) かつ \(P^0_j>P^0_i\)

上の条件をみたす整数の組 \((i,j)\) について、最初の時点で \(P^0_j\) は \(P^0_i\) より左側にあり、ソート後の列において \(P^0_j\) は \(P^0_i\) より右側にあるため、ある操作によって \(P^0_j\) は \(P^0_i\) と交換される必要があります。よって、\(P^0_i\) は少なくとも \(A_i\) 回操作によって左に動く必要があり、\(P^0_i\) を右に動かすような操作によって、それらの左に動かす操作のコストが減ることはないため、「 \(P^0_i\) を左に動かすような操作についてのコストの総和」は \((i-1)+(i-2)+\cdots+(i-A_i)=\frac{A_i(2i-A_i-1)}{2}\) 以上となります。よって、ソートに必要なコストの総和は

\[ \displaystyle\sum_{i=1}^N \frac{A_i(2i-A_i-1)}{2} \]

以上となります。

一方でこれをみたすように操作を行う事ができます。
具体的には、次の操作を\(i=N,N-1, \ldots, 1\) の順で行えば良いです。

\(i\) を \(P_i=i\) になるまで移動させる。
より厳密には、\(P_j=i\) である \(j\)を選び、\(P_j\) と \(P_{j+1}\) の交換、\(P_{j+1}\) と \(P_{j+2}\) の交換、\(\ldots\)、\(P_{i-1}\) と \(P_i\) の交換をこの順で行う。
ここで、ある \(i=i_0\) について操作を行う時点で、\(i_0<i'\leq N\) について \(P_{i'}=i'\) が成り立っていることから、上記の \(j\) は \(j\leq i_0\) をみたすことに注意せよ。

このように \(P\) に対して操作を行ったとき、各 \(i\) について、\(P^0_i\) を \(P_{P^0_i}\) まで動かす操作では常に \(P^0_i\) を右に動かしており、以降の操作で動くことはないため、\(P^0_i\) が左に動くのはそれ以前の部分しかあり得ません。すなわち、\(P^0_j>P^0_i\) かつ \(j<i\) をみたす \(j\) について、\(P^0_j\) を \(P_{P^0_j}\) まで動かす過程でのみ左に動きます。\(P^0_i\) が左に動く回数は操作方法よりちょうど \(A_i\) 回であり、またこれらの操作の間に\(P^0_i\) が右に動くことはないことから、「 \(P^0_i\) を左に動かすような操作についてのコストの総和」は \(\frac{A_i(2i-A_i-1)}{2}\) となります。

ゆえに、 \( \displaystyle\sum_{i=1}^N \frac{A_i(2i-A_i-1)}{2} \) の値を求めれば良いです。
\(A_i\) はFenwick tree などのデータ構造を用いることで、\(O(N\log N)\) で求める事ができるため、これをもとに答えを計算すれば良く、問題の制約下でこれは十分高速です。
よって、この問題を解く事ができました。

c++ による実装例:

#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using namespace atcoder;

int main() {
    int n;
    cin>>n;
    vector<int>p(n);
    for(int i=0;i<n;i++)cin>>p[i];
  
    fenwick_tree<int> fw(n);
    long long ans=0,a;
  
    for(int i=0;i<n;i++){
        a=fw.sum(p[i],n);
        ans+=(a*(2*i-a+1))/2;
        fw.add(p[i]-1,1);
    }
	
    cout<<ans<<endl;
    return 0;
}