For "next greater element," use a monotonic decreasing stack (biggest on bottom).
When you pop an element because the current element is larger, you've found the answer for the popped element.
The current element is its "next greater." Elements that are never popped (they're bigger than everything after them) have no next greater. They stay on the stack until the end.
Each element is pushed once and popped at most once. Total: .