05AB1E, 23 bytes
ā<œε©2.ÆíÆ.±Iε®Nèè}«P}O
Port of @LeakyNun's Jelly answer.
Try it online or verify all but one test cases (the biggest test case times out on TIO).
Explanation:
ā # Push a list in the range [1, (implicit) input-length]
< # Decrease it by 1 to make the range [0, input-length)
œ # Get all permutations of this list
ε # Map each permutation to:
© # Store the permutation in variable `®` (without popping)
2.Æ # Get all 2-element combinations of this list
í # Reverse each inner list
Æ # Reduce each by subtraction
.± # And take their signum (-1 if a<0; 0 if a==0; 1 if a>0)
I # Push the input
ε # Map each row to:
® # Get the current permutation from variable `®`
Nè # Use the map-index to index into this permutation
è # And use that to index into the row
}« # After the map: merge the two lists together
P # And take its product
}O # After the outer map: sum all value
# (after which it is output implicitly as result)
