[C++] Simplest Intuitive Solution | O(n)
For nums[i] to be greater than nums[j] for all 0 <= j < i & less than nums[k] for all i < k <= n-1, it is enough if nums[i] is greater than the largest element 
* For ```nums[i]``` to be greater than ```nums[j]``` for all ```0 <= j < i``` & less than nums[k] for all ```i < k <= n-1```, it is enough if nums[i] is greater than the largest element on it\'s left & smaller than the smallest element on it\'s right. Than we add +2 to ```beauty``` at every such ```i```.\n* For this, we need to keep track of ```max``` element seen so far on the left & minimum most element on the right. \n* We can compute maximum element as we go but we need to precompute the minimum most element on the right of an index ```i```.\n* If the above condition doesn\'t hold, we check whether ```nums[i] > nums[i-1]``` && ```nums[i] < nums[i+1]```, if so we add +1 to ```beauty```.\n* If neither of these conditions hold, we move on to the next element.\n\n**Time Complexity :** O(n) - Two-pass solution \n\n**Space Complexity :** O(n) - for ```mini``` array\n\n**Code :**\n```\nclass Solution {\npublic:\n    int sumOfBeauties(vector<int>& nums) {\n        int n = nums.size(), maxi = nums[0], beauty = 0;\n        vector<int> mini(n, INT_MAX); //mini[i] stores the least element until i from n-1\n        mini[n-1] = nums[n-1];\n        \n        for(int i=n-2; i>=0; i--) mini[i] = min(nums[i], mini[i+1]);\n        \n        for(int i=1; i<n-1; i++){\n            if(nums[i] > maxi && nums[i] < mini[i+1]) beauty += 2;\n            else if(nums[i] > nums[i-1] && nums[i] < nums[i+1]) beauty++;\n            maxi = max(maxi, nums[i]); //updating max so far on-the-fly\n        }\n        return beauty;\n    }\n};\n```\n
['C', 'C++']