Next Greater Element II

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Treat the array as circular: after the last element comes the first element again. For every position, find the first greater value encountered when moving right around the circle. The element itself cannot be used as its own answer. If no greater value exists, print $-1$.

Input

The first line contains $n$. The second line contains the $n$ array values.

Output

Print $n$ integers, the circular next greater value for each position, or $-1$.

Subtasks

• Subtask 1 (30 points): $n\le200$; all other conditions are unchanged.
• Subtask 2 (70 points): $1\le n\le10^4$, $-10^9\le nums_i\le10^9$.

Examples

Input

3
1 2 1

Output

2 -1 2

Explanation

The circular array is $[1,2,1]$.

• For the $1$ at position $1$, moving right immediately reaches $2>1$, so the answer is $2$.
• For the $2$ at position $2$, moving right visits the $1$ at position $3$ and then wraps to the $1$ at position $1$; neither is greater than $2$, so the answer is $-1$.
• For the $1$ at position $3$, wrapping around first reaches the equal value $1$ at position $1$, then reaches $2>1$ at position $2$, so the answer is $2$.

Therefore the output is 2 -1 2.