Given an array of package weights, where weights[i] represents weight of package i, find sum of the differences between min and max weights of all possible contiguous shipments.
Example 1, weights = [1,2,3]
Below are the contiguous shipments possible for these three packages:

1. 1 (Only first package in this shipment with wight 1. Min package weight = 1, Max package weight = 1, diff = 0)
2. 2 (Only first package in this shipment with wight 2. Min package weight = 2, Max package weight = 2, diff = 0)
3. 3 (Only first package in this shipment with wight 3. Min package weight = 3, Max package weight = 3, diff = 0)
4. 1,2 (Two packages in this shipment with wight 1 & 2. Min package weight = 1, Max package weight = 2, diff = 1)
5. 1,2,3 (Three packages in this shipment with wight 1,2 & 3. Min package weight = 1, Max package weight = 3, diff = 2)
6. 2,3 (Two packages in this shipment with wight 2 & 3. Min package weight = 2, Max package weight = 3, diff = 1)

Therefore the final sum is = 0+0+0+1+2+1 = 4

Example 2, weights = [3,2,3]
Below are the contiguous shipments possible for these three packages:

1. 3 (Only first package in this shipment with wight 3. Min package weight = 3, Max package weight = 1, diff = 0)
2. 2 (Only first package in this shipment with wight 2. Min package weight = 2, Max package weight = 1, diff = 0)
3. 3 (Only first package in this shipment with wight 3. Min package weight = 3, Max package weight = 1, diff = 0)
4. 3,2 (Two packages in this shipment with wight 3 & 2. Min package weight = 2, Max package weight = 3, diff = 1)
5. 3,2,3 (Three packages in this shipment with wight 3,2 & 3. Min package weight = 2, Max package weight = 3, diff = 1)
6. 2,3 (Two packages in this shipment with wight 2 & 3. Min package weight = 2, Max package weight = 3, diff = 1)

Therefore final sum is = 0+0+0+1+1+1 = 3

How could we solve this in less than O(n^2) ?