Next Greater Elements

Given an unsorted array of integers, for each element, find the first greater element on its right. In other words, for each index (i) (with (0 \leq i < n)) in the array (a), determine the smallest index (j) such that (j > i) and (a[j] > a[i]). If no such (j) exists, output (-1) for that element.

For example, given the array [4, 5, 2, 25], the next greater elements are [5, 25, 25, -1].

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) denoting the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Print to standard output (stdout) a single line containing (n) space-separated integers, where each integer is the next greater element of the corresponding input element. If it does not exist, print -1.## sample

4
4 5 2 25

5 25 25 -1