You are given a 0-indexed integer array nums. For each index i (1 &lt;= i &lt;= nums.length - 2) the beauty of nums[i] equals:


	2, if nums[j] &lt; nums[i] &lt; nums[k], for all 0 &lt;= j &lt; i and for all i &lt; k &lt;= nums.length - 1.
	1, if nums[i - 1] &lt; nums[i] &lt; nums[i + 1], and the previous condition is not satisfied.
	0, if none of the previous conditions holds.


Return the sum of beauty of all nums[i] where 1 &lt;= i &lt;= nums.length - 2.

&nbsp;
Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: For each index i in the range 1 &lt;= i &lt;= 1:
- The beauty of nums[1] equals 2.


Example 2:

Input: nums = [2,4,6,4]
Output: 1
Explanation: For each index i in the range 1 &lt;= i &lt;= 2:
- The beauty of nums[1] equals 1.
- The beauty of nums[2] equals 0.


Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: For each index i in the range 1 &lt;= i &lt;= 1:
- The beauty of nums[1] equals 0.


&nbsp;
Constraints:


	3 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i] &lt;= 105


class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n = len(nums)
        max_dp = [0] * n
        min_dp = [float(inf)] * n
        max_dp[0] = nums[0]
        min_dp[-1] = nums[-1]
        
        for i in range(1, n):
            max_dp[i] = max(nums[i], max_dp[i-1])
            
        for i in range(n-2, -1, -1):
            min_dp[i] = min(nums[i], min_dp[i+1])
        
        ans = 0
        for i in range(1, n-1):
            if max_dp[i-1] < max_dp[i] and nums[i] < min_dp[i+1]:
                ans += 2
            elif nums[i-1] < nums[i] < nums[i+1]:
                ans += 1
        return ans
class Solution {
    public int sumOfBeauties(int[] nums) {
        boolean[] left = new boolean[nums.length];
        boolean[] right = new boolean[nums.length];

        left[0] = true;
        int leftMax = nums[0];
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] > leftMax) {
                left[i] = true;
                leftMax = nums[i];
            }
        }

        right[nums.length-1] = true;
        int rightMin = nums[nums.length-1];
        for(int i = nums.length-2; i >= 0; i--) {
            if(nums[i] < rightMin) {
                right[i] = true;
                rightMin = nums[i];
            }
        }

        int beautyCount = 0;
        for(int i = 1; i < nums.length-1; i++) {
            if(left[i] && right[i]) {
                beautyCount += 2;
            }

            else if(nums[i-1] < nums[i] && nums[i] < nums[i+1]) {
                beautyCount += 1;
            }

        }
        return beautyCount;
    }
}
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n=nums.size();
        vector<int>right;
        vector<int>left;
        int low=nums[0];
        for(int i=0;i<nums.size();i++){
            
            left.push_back(low);
            low=max(low,nums[i]);
        }
        low=nums[n-1];
        for(int i=n-1;i>=0;i--){
            
            right.push_back(low);
            low=min(low,nums[i]);
        }
        reverse(right.begin(),right.end());
        int ans=0;
        for(int i=1;i<n-1;i++){
            if(nums[i]>left[i] && nums[i]<right[i]){
                ans+=2;
            }
            else if(nums[i]>nums[i-1] && nums[i]<nums[i+1]){
                ans+=1;
            }
            else{
                ans+=0;
            }
        }
        return ans;
        
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var sumOfBeauties = function(nums) {
    let min = nums[0], max = Infinity, maxArr = [], total = 0;

    // Creating an array, which will keep the record of minimum values from last index
    for(let i=nums.length-1; i>1; i--) {
        if(nums[i] < max) max = nums[i];
        maxArr.push(max);
    }

    // iterating through array to check the given conditions
    for(let i=1; i<nums.length-1; i++) {

        // Keeping a record of max value from all index < i
        if(nums[i-1] > min) min = nums[i-1];

        // Checking conditions
        if(nums[i] < maxArr.pop() && min < nums[i]) total += 2;
        else if(nums[i-1] < nums[i] && nums[i] < nums[i+1]) total += 1;
    }

    return total;
};
Sum of Beauty in the Array