In what follows, imagine the permutation lined up in a single row from left to right, with smaller indices on the left and larger indices on the right. To distinguish it from the permutation at any point during the operations, let us write the initially given (input) permutation \(P_i\) as \(P^0_i\).

Consider evaluating from below the minimum total cost required to sort \(P\).
The total cost required to sort \(P\) can be computed as the sum over each element of \(P\) of the total cost of the operations that move that element to the left (i.e., swapping it with the element immediately to its left).
Define, for \(1 \leq i \leq N\), the value \(A_i\) to be the number of integers \(j\) satisfying the condition:

• \(1 \leq j \leq i-1\) and \(P^0_j > P^0_i\).

For each pair \((i, j)\) satisfying the above condition, we note that in the initial state, \(P^0_j\) is to the left of \(P^0_i\), but in the sorted array, \(P^0_j\) must be to the right of \(P^0_i\). Therefore, in some operation, \(P^0_j\) must be swapped with \(P^0_i\), which implies that \(P^0_i\) must be moved to the left at least \(A_i\) times. Further, moving \(P^0_i\) to the right does not reduce any of the costs for these leftward moves. Hence, “the total cost of the operations that move \(P^0_i\) to the left” is at least \((i-1) + (i-2) + \cdots + (i - A_i) = \frac{A_i(2i - A_i - 1)}{2}\). Therefore, the total cost needed to sort the permutation is at least

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

On the other hand, there is a way to perform the operations so that this bound is achieved.
Concretely, we can perform the following operations in the order \(i = N, N-1, \ldots, 1\):

Move \(i\) so that \(P_i = i\).
More specifically, select the position \(j\) where \(P_j = i\), and then swap \(P_j\) and \(P_{j+1}\), swap \(P_{j+1}\) and \(P_{j+2}\), \(\ldots\), and finally swap \(P_{i-1}\) and \(P_i\) in that order.
Note that when performing this procedure for some \(i = i_0\), we have \(P_{i'} = i'\) for all \(i_0 < i' \leq N\), so the selected \(j\) satisfies \(j \leq i_0\).

When these operations are performed on \(P\), for each \(i\), while moving \(P^0_i\) to position \(P_{P^0_i}\), it is always moved to the right, and it will not move again in subsequent operations. Hence, \(P^0_i\) only moves to the left before that phase. In other words, it only moves to the left while \(P^0_j\) is being moved to \(P_{P^0_j}\) for \(j\) with \(P^0_j > P^0_i\) and \(j < i\). Since \(P^0_i\) moves left exactly \(A_i\) times and does not move to the right during those operations, the total cost of the operations that move \(P^0_i\) to the left is \(\frac{A_i(2i - A_i - 1)}{2}\).

Therefore, we only need to compute

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

We can find \(A_i\) in \(O(N \log N)\) time by using data structures such as a Fenwick tree, then compute the answer. This is fast enough under the problem constraints.
Hence, the problem can be solved.

Sample implementation in 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 * (2LL * i - a + 1)) / 2;
        fw.add(p[i] - 1, 1);
    }
	
    cout << ans << endl;
    return 0;
}