Phần tử lớn hơn tiếp theo (Next Greater Element)

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$. Với mỗi vị trí $i$, phần tử lớn hơn tiếp theo là phần tử đầu tiên ở bên phải có giá trị lớn hơn $A_i$. Nếu không có phần tử như vậy, kết quả tại vị trí $i$ 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ị, trong đó giá trị thứ $i$ là phần tử lớn hơn tiếp theo của $A_i$, hoặc $-1$ nếu không tồn tại.

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

4
3 5 2 7

Output

5 7 7 -1

Giải thích

Dãy là $3,5,2,7$.

• Với $A_1=3$, phần tử đầu tiên bên phải lớn hơn $3$ là $5$, nên kết quả thứ nhất là $5$.
• Với $A_2=5$, phần tử $2$ không lớn hơn $5$, còn $7>5$, nên kết quả thứ hai là $7$.
• Với $A_3=2$, phần tử ngay bên phải là $7>2$, nên kết quả thứ ba là $7$.
• Với $A_4=7$, không còn phần tử nào ở bên phải, nên kết quả là $-1$.

Do đó chương trình in 5 7 7 -1.