I am trying to make an algorithm that calculates the sum of each maximum element in a subarray not including the first and last elements. The naive approach is obvious but I do not want that.

Here is an example if it is not clear so far:

total = 0
arr = [4, 3, 5, 2, 8, 1]

We start with elements 4 and 5, 3 is the only number so it is the maximum and so the total so far is 3. We then take 4 and 2 and the maximum in between them is 5 so we add it to the total. We take 4 and 8 and 5 is still the maximum so our current total is now 13. Taking 4 and 1 we have a maximum element of 8 so we add 8 to the total which is now 21. Moving to 3 and 2 (since there is no element in between 3 and 5) the maximum is 5 and so we add 5 to the total. Essentially, we will just keep on adding the maximum element in between each possible subarray. How can I do this efficiently?

I already tried the O(n^2) approach clearly that is inefficient and I would like to know a better way to solve this problem. Maybe through a stack or pointers? I am not really sure. I am trying to learn DSA as an advance study for my upcoming dsa course in my university