簡単のため、0-indexedで考えます。

まず、目的の式を

\[\displaystyle \sum_{0\le i < j< N}\max(A_j-A_i,0) = \sum_{0\le i < j< N}\left\{ \max\left(A_j,A_i \right)-A_i\right\} = \sum_{0\le i < j< N}\max\left(A_j,A_i \right)-\sum_{0\le i < j< N}A_i\]

と式変形します。

ここで、一項目（maxの方）は全ての大きさ \(2\) のインデックスの集合 \(\{i,j\}\) に対する \(\displaystyle \max\left(A_i,A_j\right)\) の総和と捉えられるので、この総和は \(A\) の順番によらないことがわかります。これにより、 \(A\) を昇順にソートしたものを \(B\) とおくと、

\[ \begin{aligned} &\phantom{=} \sum_{0\le i < j< N} \max\left(A_j,A_i \right)\\ &= \sum_{0\le i < j< N} \max\left(B_j,B_i \right)\\ &=\sum_{0\le i < j< N} B_j\\ &=\sum_{j=0}^{N-1} jB_j \end{aligned} \]

として求めることができます。

一方、二項目（\(A_i\) の方）も同様に式変形をすると、

\[ \sum_{0\le i < j< N} A_i=\sum_{i=0}^{N-1} (N-1-i)A_i \]

となるので、最終的に求める値は

\[\sum_{i=0}^{N-1} iB_i -\sum_{i=0}^{N-1} (N-1-i)A_i\]

と表すことができます。この値は配列のソートを用いることで簡単に求めることができます。

以上でこの問題が解けました。計算量はソートがボトルネックとなり \(O(N\log N)\) となります。

実装例(Python3)

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
ans = 0
for i in range(N):
  ans += i * B[i]
  ans -= (N - 1 - i) * A[i]
print(ans)