Next Greater Frequency

Source: Baekjoon Online Judge

Version: Phuoc Hung OJ Extended

Problem Statement

Given an array $A_1,A_2,\ldots,A_N$. Let $F(x)$ be the number of occurrences of value $x$ in the entire array. For every position $i$, find the first $A_j$ to its right such that $F(A_j)>F(A_i)$. If it does not exist, the answer 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 element whose global frequency is greater than that of $A_i$, or $-1$ if none exists.

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

7
1 1 2 3 4 2 1

Output

-1 -1 1 2 2 1 -1

Explanation

First count occurrences in the entire array:

• $F(1)=3$;
• $F(2)=2$;
• $F(3)=1$;
• $F(4)=1$.

Now inspect each position:

• The first two values are $1$ with frequency $3$, the maximum frequency in the array, so both answers are $-1$.
• For the value $2$ at position $3$, the following values $3,4,2$ do not have a greater frequency; the final $1$ has frequency $3>2$, so the answer is $1$.
• For the value $3$ at position $4$, the next value $4$ also has frequency $1$, while the following $2$ has frequency $2>1$, so the answer is $2$.
• For the value $4$ at position $5$, the next $2$ has frequency $2>1$, so the answer is $2$.
• For the value $2$ at position $6$, the final $1$ has frequency $3>2$, so the answer is $1$.
• The final $1$ has no element to its right, so its answer is $-1$.

Thus the output is -1 -1 1 2 2 1 -1.