Sum of Differences in Subarrays

Given an array of \(n\) integers, your task is to compute the sum of the differences between the maximum and minimum values for every possible contiguous subarray. For a subarray starting at index \(i\) and ending at index \(j\), define the difference as:

$$\text{diff}(i,j)=\max_{k=i}^{j}(a_k)-\min_{k=i}^{j}(a_k)$$

The final answer is the sum of \(\text{diff}(i,j)\) over all subarrays of the given array.

This problem requires a careful iteration through all possible subarrays. Although the straightforward approach has a time complexity of \(O(n^2)\), it is sufficient for the input sizes given in the test cases.

inputFormat

The first line contains a single integer \(n\) which denotes the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Output a single integer which is the sum of the differences between the maximum and minimum elements over all contiguous subarrays.

## sample

3
1 2 3

4

</p>