C++: Efficient Calculation Using Prefix and Suffix Arrays
IntuitionWe need to determine the "beauty" of each element in nums (excluding the first and last elements) based on specific conditions. The conditions require
# Intuition
We need to determine the "beauty" of each element in nums (excluding the first and last elements) based on specific conditions. The conditions require checking whether an element is between all previous elements and all next elements (for beauty 2) or simply between its immediate neighbors (for beauty 1).

To efficiently check the first condition, we can precompute two arrays:
* prefix[i]: The maximum value from the start of the array up to index i.
* suffix[i]: The minimum value from index i to the end of the array.

Using these precomputed values, we can efficiently determine whether an element satisfies the beauty conditions.

# Approach
* Precompute prefix and suffix:
    * prefix[i] stores the maximum value from nums[0] to nums[i].
    * suffix[i] stores the minimum value from nums[i] to nums[n-1].
* Iterate through the array (1 ≤ i ≤ n-2) and determine beauty values:
    * If prefix[i-1] < nums[i] < suffix[i+1], add 2 to the result.
    * Else, if nums[i-1] < nums[i] < nums[i+1], add 1 to the result.

# Complexity
- Time complexity: $$O(n)$$
- Space complexity: $$O(n)$$

# Code
```cpp []
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        std::vector<int> prefix(n), suffix(n);
        prefix[0] = nums[0];
        suffix[n - 1] = nums[n - 1];

        for (int i{1}, j{n - 2}; i < n; ++i, --j) {
            prefix[i] = std::max(prefix[i - 1], nums[i]);
            suffix[j] = std::min(suffix[j + 1], nums[j]);
        }

        int res{};
        for (int i{1}; i < n - 1; ++i) {
            if (prefix[i - 1] < nums[i] && nums[i] < suffix[i + 1]) res += 2;
            else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) ++res;
        }

        return res;
    }
};
```
['C++']