Hi! I have been trying the following problem for some time now and haven't been able to come up with a solution better than O(N^2).

Given an array A with N integers, define *max*_{i, j} to be the maximum value in *A*[*i*..*j*] and *min*_{i, j} to be the minimum value in *A*[*i*..*j*]. *A*[*i*..*j*] denotes the subarray starting from index *i* and ending at *j*. Compute the following sum:

Please let me know if this problem is available on some OJ.