Next Greater Element

Interview

Time limit1sMemory limit512 MB

Summary

For each element of a sequence, output the nearest greater value to its right, or -1 if none exists.

Level: Medium5 of 10
Topics: Stack, Array, Two pointers, Implementation
Solved: No attempts yet

Problem

There is a sequence A = A1, A2, ..., AN of size N. For each element Ai of the sequence, find its next greater element NGE(i). The next greater element of Ai is the leftmost number to the right of Ai that is greater than Ai. If no such number exists, the next greater element is -1.

For example, if A = [3, 5, 2, 7], then NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, and NGE(4) = -1. If A = [9, 5, 4, 8], then NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, and NGE(4) = -1.

Input

The first line gives the size N of the sequence A (1 ≤ N ≤ 1,000,000). The second line gives the elements A1, A2, ..., AN of the sequence A (1 ≤ Ai ≤ 1,000,000).

Output

Print the N numbers NGE(1), NGE(2), ..., NGE(N), separated by spaces.

Examples2

Example 1
Input
```
4
3 5 2 7
```
Expected output
```
5 7 7 -1
```
Example 2
Input
```
4
9 5 4 8
```
Expected output
```
-1 8 8 -1
```