Frequency-Greater Next Element

There is a sequence $A = A_1, A_2, \cdots, A_N$ of size $N$. For each element $A_i$ of the sequence, we want to find its frequency-greater next element $NGF(i)$.

Let $F(A_i)$ be the number of times $A_i$ appears in $A$. The frequency-greater next element of $A_i$ is the leftmost number to its right whose number of appearances in $A$ is greater than $F(A_i)$. If no such number exists, the frequency-greater next element is $-1$.

For example, if $A = [1, 1, 2, 3, 4, 2, 1]$, then $F(1) = 3$, $F(2) = 2$, $F(3) = 1$, and $F(4) = 1$. To the right of $A_1$ there is no number that appears more than 3 times, so $NGF(1) = -1$. For $A_3$, $A_7$ lies to its right and $F(A_3 = 2) < F(A_7 = 1)$, so $NGF(3) = 1$. We have $NGF(4) = 2$, $NGF(5) = 2$, and $NGF(6) = 1$.

The first line gives the size $N$ of the sequence $A$ ($1 \le N \le 1{,}000{,}000$). The second line gives the elements $A_1, A_2, \cdots, A_N$ of $A$ ($1 \le A_i \le 1{,}000{,}000$).

Print the $N$ numbers $NGF(1), NGF(2), \cdots, NGF(N)$ separated by spaces.