I think I have a solution. **The idea is to determine the contribution of each element to the final answer.**

Note that we can get the range [l, r] for which a given element holds the maximum value using a *stack* in O(n) time (the idea is based on this). Now, the task which remains is to get the lengths of the subarrays.

Letâ€™s denote the current elementâ€™s position in the array by pos and its value by val.

We have to determine the lengths of the subarrays [i, j] in the range [l, r] such that l <= i, j <= r and i <= pos <= j. Letâ€™s denote x as the length [l, pos] and y as the length [pos, r].

Then, we can say that we need the sum of the lengths of the subarrays [pos, pos], [pos, pos+1], ..., [pos, r], [pos -1, pos], [pos -1, pos + 1], ..., [pos - 1, r], [pos - 2, pos], ..., [l, r].

Observe the pattern hereâ€¦ This sum can be expressed as (\sum_{i=1}^{x}i ) \times y + (\sum_{i=1}^{y-1}i ) \times x.

So, the contribution for the current element becomes val \times ((\sum_{i=1}^{x}i ) \times y + (\sum_{i=1}^{y-1}i ) \times x). Note that this value can be calculated in O(1). The final answer can be calculated by simply summing the contribution of each element. So, the final complexity is O(n).

**Example:**

arr = [1, 2, 3]

for 1 â†’ x = 1 and y = 1 so its contribution = 1 \times ((\sum_{i=1}^{1}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 1) = 1

for 2 â†’ x = 2 and y = 1 so its contribution = 2 \times ((\sum_{i=1}^{2}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 2) = 6

for 3 â†’ x = 3 and y = 1 so its contribution = 3 \times ((\sum_{i=1}^{3}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 3) = 18

So, the final answer = 1 + 6 + 18 = 25

Code