2012. Sum of Beauty in the Array

T: O(n)

S: O(n)

```java
class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMin = new int[n];
        Arrays.fill(rightMin, Integer.MAX_VALUE);
        
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], nums[i-1]);
        }
        for (int i = n-2; i >= 0; i--) {
            rightMin[i] = Math.min(rightMin[i+1], nums[i+1]);
        }
        int result = 0;
        for (int i = 1; i < n-1; i++) {
            if (leftMax[i] < nums[i] && nums[i] < rightMin[i]) {
                result += 2;
            } else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) {
                result++;
            }
        }
        return result;
    }
}

/**
 1 2 3
 0 1 2
 2 3 0

 2 4 6 4
 0 2 4 6
 4 4 4 0
 */
```