Monotonic Stack + Heap - Video Solution
You can watch the video solution here \n\nFirst we are finding the Next Greater Element for all numbers.\n\nWe are considering it as the middle number.\nThen we
You can watch the video solution [here](https://youtu.be/YZrQrQehM64) \n\nFirst we are finding the `Next Greater Element` for all numbers.\n\nWe are considering it as the middle number.\nThen we are adding all the numbers to the left of it in a minheap.\nAll the numbers to the right are then compared with the top element in the heap.\n\nIf it is greater, then that number is the `2nd Greater Element`.\n\n```\nclass Solution:\n    def secondGreaterElement(self, A: List[int]) -> List[int]:\n        n = len(A)\n        \n        middle, st = [[] for _ in range(n)], []\n        \n        for i in range(n):\n            while st and A[st[-1]]<A[i]:\n                middle[i].append(st.pop())\n            st.append(i)\n            \n        ans = [-1] * n\n        h = []\n        \n        for i in range(n):\n            while h and A[h[0][1]]<A[i]:\n                ans[heapq.heappop(h)[1]] = A[i]\n                \n            for j in middle[i]:\n                heapq.heappush(h, (A[j], j))\n        return ans
['Stack', 'Heap (Priority Queue)', 'Python']