C++||O(n)||Prefix and Suffix arrays|| Detailed Explaination
Please upvote if found helpful\n\nIdea is simple, just maintain the prefixMax array and SuffixMix array which will store the maximum element in the range [0,i-1
**Please upvote if found helpful**\n\nIdea is simple, just maintain the prefixMax array and SuffixMix array which will store the maximum element in the range [0,i-1] and minimum element in the range [i+1,n-1] respectively.\nIf nums[i]>prefixMax[i] it implies its greater than all the elements to its left and if nums[i]<suffixMin[i] it implies its less than all the elemnts to its right. If this condition doesn\'t get satisfied then we\'ll check if nums[i-1]<nums[i]<nums[i+1] and increment the answer accordingly.\n```\nclass Solution {\npublic:\n    int sumOfBeauties(vector<int>& nums) {\n        int n=nums.size();\n        vector<int> prefixMax(n);\n        vector<int> suffixMin(n);\n        prefixMax[0]=INT_MIN;\n        suffixMin[n-1]=INT_MAX;\n        int ans=0;\n        \n        for(int i=1;i<n;i++) prefixMax[i]=max(prefixMax[i-1],nums[i-1]);\n        for(int i=n-2;i>=0;i--) suffixMin[i]=min(suffixMin[i+1],nums[i+1]);\n        \n        for(int i=1;i<n-1;i++){\n            if(nums[i]>prefixMax[i]&&nums[i]<suffixMin[i]) ans+=2;\n            else if(nums[i]>nums[i-1]&&nums[i]<nums[i+1]) ans+=1;\n        }\n        \n        return ans;\n        \n    }\n};\n```
[]