Problema subsecvente

[•andunhill]

Enuntul: " Let’s define a value of a sequence as the difference between the largest and the smallest number within that sequence. For example, value of sequence (3, 1, 7, 2) is 6, and value of (42, 42) is 0. Find the sum of values of all subsequences of consecutive elements of a given sequence. "
(2 ≤ N ≤ 300 000)
Imi dati si mie niste idei? Eu ma gandeam sa tin un arbore de intervale in care sa retin maximul si minimul din fiecare interval apoi sa iau fiecare subsecv si sa calculez , dar nu cred ca se incadreaza in timp. (limita 1 s, 64 MB).