Phần tử có tần suất lớn hơn tiếp theo (Next Greater Frequency)

Nguồn: Baekjoon Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $A_1,A_2,\ldots,A_N$. Gọi $F(x)$ là số lần giá trị $x$ xuất hiện trong toàn bộ dãy. Với mỗi vị trí $i$, hãy tìm phần tử đầu tiên $A_j$ ở bên phải sao cho $F(A_j)>F(A_i)$. Nếu không tồn tại, kết quả là $-1$.

Input

Dòng đầu chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In $N$ giá trị. Giá trị thứ $i$ là phần tử có tần suất lớn hơn tiếp theo của $A_i$, hoặc $-1$ nếu không có.

Subtask

• Subtask 1 (30 điểm): $N\le2000$; các điều kiện khác giữ nguyên.
• Subtask 2 (70 điểm): $1\le N\le10^6$, $1\le A_i\le10^6$.

Ví dụ

Input

7
1 1 2 3 4 2 1

Output

-1 -1 1 2 2 1 -1

Giải thích

Trước hết đếm số lần xuất hiện trong toàn bộ dãy:

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

Xét từng vị trí:

• Hai số $1$ đầu tiên có tần suất $3$, là tần suất lớn nhất trong dãy, nên đều nhận $-1$.
• Với số $2$ ở vị trí $3$, các số $3,4,2$ phía sau có tần suất không lớn hơn $2$; số $1$ cuối có tần suất $3>2$, nên nhận $1$.
• Với số $3$ ở vị trí $4$, số $4$ kế tiếp cũng chỉ có tần suất $1$, còn số $2$ sau đó có tần suất $2>1$, nên nhận $2$.
• Với số $4$ ở vị trí $5$, số $2$ ngay sau có tần suất $2>1$, nên nhận $2$.
• Với số $2$ ở vị trí $6$, số $1$ cuối có tần suất $3>2$, nên nhận $1$.
• Số $1$ cuối cùng không có phần tử phía sau, nên nhận $-1$.

Kết quả là -1 -1 1 2 2 1 -1.