Next Greater Node in Linked List

You are given the head of a singly linked list containing N nodes.

For every node in the list, find the next node to its right that has a strictly greater value.

• If such a node exists, return its value.

• Otherwise, return -1 for that node.

Your task is to return an array where the i-th element represents the next greater node value for the i-th node in the linked list.

The solution should be efficient since the linked list size can be very large.

A naive approach that compares every node with all nodes to its right may lead to poor performance.

The expected solution should use an efficient data structure such as a stack to achieve linear time complexity.

📥 Input Format

• The first line contains an integer N — the number of nodes in the linked list.

• The second line contains N space-separated integers representing the values of the nodes.

📤 Output Format

Return N space-separated integers where:

• The i-th integer represents the next greater node value for the i-th node.

• If no greater node exists, return -1.

🧪 Example 1

Input

5
2 1 5 3 4

Output

5 5 -1 4 -1

Explanation

• Next greater value for 2 is 5

• Next greater value for 1 is 5

• 5 has no greater value to its right

• Next greater value for 3 is 4

• 4 has no greater value to its right

Constraints

• 1 ≤ N ≤ 200000

• -10^9 ≤ Node Value ≤ 10^9

⚡ Expected Complexity

• Time Complexity: O(N)

• Space Complexity: O(N)