The key observation follows: instead of calculating the sum of difference values of all contiguous subsequences, we can separately calculate the sum of all maximum values and all minimum values of the subsequences, subtracting the second from the first number to obtain the solution. It is not difficult to show that this approach is correct, since the difference value of a given subsequence is defined as the difference between its maximum and minimum value, thus the observation follows from addition associativity and commutativity. Here we will only describe a method to find the sum of maximum values; the sum of minimum values is obtained with a completely analogous algorithm.

Our approach is as follows: for each element of the provided sequence, we shall compute the number of contiguous subsequences that contain that element as their maximum. In order to resolve ambiguity, we shall define the first out of multiple equal maximal elements as the maximum of a subsequence.

If the position of the current element is ~K~, and its value equals ~X~, we need to find the first element to the left of it with value greater than or equal to ~X~ and the first element to the right with value strictly greater than ~X~. If the two elements satisfying the given conditions are in positions ~A~ and ~B~ respectively, then ~X~ is the maximum element in exactly those contiguous subsequences that start at positions between ~A+1~ and ~K~ (inclusive) and end at positions between ~K~ and ~B-1~ (inclusive). There are exactly ~(K-A) \times (B-K)~ such subsequences, since we multiply the number of possible choices of the first element (~K-A~) with the number of possible choices of the last one (~B-K~) in the subsequence. Hence the sum of maximum values is increased by ~X \times (K-A) \times (B-K)~.

Now we only need an algorithm to find the first element to the left of the current one that is greater than or equal to it (the algorithms to find the first one to the right that is greater, as well as the other combinations for finding minimum values, are completely analogous). We shall traverse the sequence from left to right, keeping a stack of pairs (value, position) containing some previous elements of the sequence. The stack will be kept in decreasing order of the values. Processing of an element with value ~X~ consists of popping all elements with values strictly less than ~X~ from the stack. The element that remains at the top of the stack (if any) is precisely the first one to the left of ~X~ that is greater than or equal to it. After that, the element ~X~ is pushed on top of the stack and the algorithm continues with the next element of the sequence.