Python [max/min heap]
Max heap for left hand side.\nMin heap for right hand side. Also pop lazily.\n\nTime: O(N logN)\nSpace: O(N)\n\npython\nclass Solution:\n    def sumOfBeauties(s
Max heap for left hand side.\nMin heap for right hand side. Also pop lazily.\n\nTime: `O(N logN)`\nSpace: `O(N)`\n\n```python\nclass Solution:\n    def sumOfBeauties(self, A):\n        if len(A) <= 2: return 0\n        \n        # max heap for left side\n        max_heap = []\n        heapq.heappush(max_heap, -A[0])\n        \n        #lazy min heap for right side\n        #so you also need to keep track of counts\n        min_heap = []\n        counts = collections.defaultdict(int)\n        for i in range(2, len(A)):\n            heapq.heappush(min_heap, A[i])\n        \n        ans = 0\n        for i in range(1, len(A) - 1):\n            if -max_heap[0] < A[i] < min_heap[0]:\n                ans += 2\n            elif A[i - 1] < A[i] < A[i + 1]:\n                ans += 1\n            \n            #left side\n            heapq.heappush(max_heap, -A[i])\n            \n            #right side\n            counts[A[i + 1]] += 1\n            while min_heap and counts[min_heap[0]] > 0:\n                counts[min_heap[0]] -= 1\n                heapq.heappop(min_heap)\n        \n        return ans\n```
[]