Next greater Element

Given an array, print the Next Greater Element for every element.

The Next Greater Element for an element $x$ is the first greater element on the right side of $x$ in the array. Elements for which no greater element exist, consider the next greater element as $-1$.

Input

The first line contains number $n(n\le 10^5)$. The second line contains $n$ positive integers, each not greater than $10^9$.

Output

For each element of input array print the Next Greater Element.

Examples