• 1 <= arr.length <= 3 × 10⁴
• 1 <= arr[i] <= 3 × 10⁴

To understand the optimal solution, we must first see why the natural approach fails as the array grows.

The most direct way is to look at every possible contiguous subarray, find its minimum, and add it to a running total.

total_sum = 0
n = len(arr)
for i in range(n):
    min_val = arr[i]
    for j in range(i, n):
        # Update minimum for current subarray arr[i...j]
        min_val = min(min_val, arr[j])
        total_sum += min_val
return total_sum % (10**9 + 7)

With an array of size 30,000, there are nearly 450 million subarrays. This quadratic approach is far too slow. To solve this efficiently, we must move from a "Subarray-First" mindset to an "Element-First" mindset.

Instead of iterating through subarrays, we ask a different question for every single number in the array:
"In how many subarrays am I the absolute minimum?"

If a number X is the minimum for K different subarrays, then its total contribution to the final sum is simply X * K. By calculating this for every element, we get our answer in linear time.

Imagine you are a number at index i. You are the "star" (the minimum) of a subarray as long as every other number in that subarray is larger than you.
- Left Boundary (L): How many steps can you look to the left before hitting a number smaller than you?
- Right Boundary (R): How many steps can you look to the right before hitting a number smaller than you?

If you can extend L positions to the left (including yourself) and R positions to the right (including yourself), the number of subarrays where you are the minimum is:
Count = L * R

Why L * R?
Think of it as choosing a start and end point. You have L choices for where the subarray can start (anywhere from your left boundary to your current position) and R choices for where it can end (anywhere from your current position to your right boundary). Every combination of these start and end points creates a unique subarray where you are the minimum.

What if the array has duplicates, like [1, 2, 1]? Both 1s will try to claim the entire array as their "Range of Influence," leading to double-counting.

To fix this, we use a Tie-Breaking Rule:
- An element claims a range to its left if the neighbors are strictly greater (>).
- An element claims a range to its right if the neighbors are greater than or equal (>=).

By being "strict" on one side and "loose" on the other, we ensure that every subarray has exactly one "owner," even if it contains multiple identical minimum values.

Finding the "nearest smaller neighbor" is the classic use case for a Monotonic Stack.
1. First Pass (Left): Find the distance to the previous smaller element for every index.
2. Second Pass (Right): Find the distance to the next smaller (or equal) element for every index.
3. Calculation: Multiply Value LeftDistance RightDistance and sum them up.

left_distance = [0] * n
right_distance = [0] * n
stack = []

// 1. Find Distance to Previous Less Element
FOR i from 0 to n-1:
    WHILE stack is NOT empty AND arr[stack.PEEK()] > arr[i]:
        stack.POP()
    left_distance[i] = i - (stack.PEEK() IF stack else -1)
    stack.PUSH(i)

stack.CLEAR()

// 2. Find Distance to Next Less Element (or Equal)
FOR i from n-1 down to 0:
    WHILE stack is NOT empty AND arr[stack.PEEK()] >= arr[i]:
        stack.POP()
    right_distance[i] = (stack.PEEK() IF stack else n) - i
    stack.PUSH(i)

// 3. Sum contributions
sum = 0
FOR i from 0 to n-1:
    sum += arr[i] * left_distance[i] * right_distance[i]
    sum %= MOD

RETURN sum