Next Greater Element

In this problem, you are given a list of integers and your task is to find the Next Greater Element (NGE) for each element. For an element ( x ), the NGE is defined as the first element to its right which is greater than ( x ). If no such element exists, then the NGE is ( -1 ).

For example, given the input list [4, 5, 2, 25], the output should be [5, 25, 25, -1] because for 4 the next greater is 5, for 5 it is 25, for 2 it is again 25, and for 25 there is no greater element so the answer is -1.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

( n )
A single integer representing the number of elements in the list.

( a_1, a_2, \dots, a_n )
A sequence of ( n ) space-separated integers.

outputFormat

The output is written to standard output (stdout) as a sequence of space-separated integers representing the Next Greater Element for each corresponding input element. If no next greater element exists for an input element, output ( -1 ) in that position.## sample

4
4 5 2 25

5 25 25 -1