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, determine 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.

This problem must be solved efficiently since the list size can be large. A naive approach comparing every node with the remaining nodes may lead to performance issues.

The expected approach should use efficient data structures such as stacks to achieve linear time complexity.

Input Format

First line contains an integer N — number of nodes in the linked list

Second line contains N space-separated integers representing node values

Output Format

Return N integers representing the next greater node value for each node in order.

If no greater node exists, return -1.

Constraints

1 ≤ N ≤ 200000

-10^9 ≤ Node Value ≤ 10^9

Time Complexity expected: O(N)

Space Complexity expected: O(N)