Next Greater Element

Source: Baekjoon Online Judge

Version: Phuoc Hung OJ Extended

Problem Statement

Given an array $A_1,A_2,\ldots,A_N$. For each position $i$, its next greater element is the first element to the right whose value is greater than $A_i$. If it does not exist, the answer at position $i$ is $-1$.

Input

The first line contains an integer $N$. The second line contains $N$ integers $A_1,A_2,\ldots,A_N$.

Output

Print $N$ values. The $i$-th value is the next greater element of $A_i$, or $-1$ if it does not exist.

Subtasks

• Subtask 1 (30 points): $N\le2000$; all other conditions are unchanged.
• Subtask 2 (70 points): $1\le N\le10^6$, $1\le A_i\le10^6$.

Examples

Input

4
3 5 2 7

Output

5 7 7 -1

Explanation

The array is $3,5,2,7$.

• For $A_1=3$, the first greater value to the right is $5$, so the first answer is $5$.
• For $A_2=5$, the value $2$ is not greater than $5$, while $7>5$, so the second answer is $7$.
• For $A_3=2$, the immediately following value is $7>2$, so the third answer is $7$.
• For $A_4=7$, there is no element to its right, so the answer is $-1$.

Therefore the output is 5 7 7 -1.