Trace [3, 1, 2, 4].
Compute left boundaries (previous smaller element):
arr[0]=3: no smaller to left.left[0] = -1.arr[1]=1: no smaller to left.left[1] = -1.arr[2]=2:arr[1]=1is smaller.left[2] = 1.arr[3]=4:arr[2]=2is smaller.left[3] = 2.
Compute right boundaries (next smaller element):
arr[0]=3:arr[1]=1is smaller.right[0] = 1.arr[1]=1: no smaller to right.right[1] = 4.arr[2]=2: no smaller to right.right[2] = 4.arr[3]=4: no smaller to right.right[3] = 4.
Contributions: 3×(0-(-1))×(1-0) = 3, 1×(1-(-1))×(4-1) = 6, 2×(2-1)×(4-2) = 4, 4×(3-2)×(4-3) = 4.
Sum = 3 + 6 + 4 + 4 = 17.
Two passes with monotonic stacks. time. space for boundary arrays.