Advanced Patterns

arr = [ 3 , 1 , 2 , 4 ]
idx     0   1   2   3

stack (indices, values increasing): []
ans = 0    MOD = 1e9+7

For each element we want:
  left[i]  = # of choices for subarray start (incl. i)
  right[i] = # of choices for subarray end   (incl. i)
contribution = arr[i] * left[i] * right[i]

Goal: sum of min over every contiguous subarray. Brute force is O(n^2). Instead, each element arr[i] is the minimum of exactly left[i]*right[i] subarrays — those bounded by its nearest smaller neighbors. Why a monotonic stack: it finds those nearest-smaller boundaries for all i in one pass.

arr = [ 3 , 1 , 2 , 4 ]
         ^i=0
stack top has nothing smaller below it.

While stack && arr[stack.top] >= 3:  (empty -> skip)
left[0] = i - (-1) = 1   (no PLE; sentinel -1)
push -> stack = [0]      (values: [3])

Stack is empty, so index 0 has no previous-less element; its left boundary is the array edge. left[0]=1 means only one subarray can start here with 3 as a candidate min: [3] itself. We pop on >= for the left side so the PLE is strictly-less, the convention that keeps equal values from being double-counted.

arr = [ 3 , 1 , 2 , 4 ]
             ^i=1
While stack && arr[stack.top]=3 >= 1:  POP index 0
  -> 3's right boundary is fixed: NLE of 3 is index 1.
stack now empty.
left[1] = i - (-1) = 2   (1 has no smaller element to its left)
push -> stack = [1]      (values: [1])

Value 1 is smaller than 3, so 3 can never be the min of any subarray extending past index 1 — we pop it, finalizing that 3's reach to the right ends here. left[1]=2: subarrays starting at index 0 or 1 can have 1 as min, since everything to the left (just 3) is larger.

arr = [ 3 , 1 , 2 , 4 ]
                 ^i=2
While stack && arr[stack.top]=1 >= 2?  1 >= 2 is FALSE -> stop.
PLE of 2 is index 1 (value 1).
left[2] = i - 1 = 1
push -> stack = [1, 2]   (values: [1, 2])

The stack top is 1, which is smaller than 2, so we stop popping — 1 is the previous-less element of 2. left[2]=1: only a subarray starting exactly at index 2 keeps 2 as min, because index 1 holds the smaller 1.

arr = [ 3 , 1 , 2 , 4 ]
                     ^i=3
While stack && arr[stack.top]=2 >= 4?  FALSE -> stop.
PLE of 4 is index 2 (value 2).
left[3] = i - 2 = 1
push -> stack = [1, 2, 3]   (values: [1, 2, 4])

Stack stays increasing [1,2,4]. 4 is the largest so far, its previous-less element is 2 at index 2, giving left[3]=1. The main loop ends; remaining stack elements never got popped, meaning their next-less-or-equal element is the right edge (sentinel n=4).

n = 4. Survivors on the stack reach the right edge (NLE = n = 4).
right[i] = NLE[i] - i.
  popped value 3: NLE was set to index 1  -> right[0] = 1 - 0 = 1
  survivor 1 (idx 1): NLE = 4            -> right[1] = 4 - 1 = 3
  survivor 2 (idx 2): NLE = 4            -> right[2] = 4 - 2 = 2
  survivor 4 (idx 3): NLE = 4            -> right[3] = 4 - 3 = 1

idx:    0    1    2    3
val:    3    1    2    4
left:   1    2    1    1
right:  1    3    2    1

Survivors 1,2,4 never found an element <= themselves to their right, so they extend to the array's end (index 4). Popped value 3 got right=1 when index 1 popped it. Why this is safe: each element's right reach stops at the first element that is less-or-equal (or the edge), while its left reach stops at the first strictly-smaller element, so no subarray is counted under two different minima.

Boundaries (PLE strictly-less on left, NLE <= on right):
idx:        0    1    2    3
val:        3    1    2    4
left:       1    2    1    1
right:      1    3    2    1
contrib = val*left*right:
  3*1*1 = 3
  1*2*3 = 6
  2*1*2 = 4
  4*1*1 = 4
--------------------------
sum = 3 + 6 + 4 + 4 = 17

Cross-check by listing every subarray min of [3,1,2,4]: 3, 1, 2, 4 (len1) + min(3,1)=1, min(1,2)=1, min(2,4)=2 (len2) + min(3,1,2)=1, min(1,2,4)=1 (len3) + min(3,1,2,4)=1 (len4) = (3+1+2+4) + (1+1+2) + (1+1) + 1 = 10 + 4 + 2 + 1 = 17. Matches. Each element was pushed and popped once, so total work is O(n).