Tháp thu tín hiệu (Tower)

Nguồn: Baekjoon Online Judge

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

Đề bài

Có $N$ tòa tháp cao khác nhau xếp từ trái sang phải, đánh số từ $1$ đến $N$. Mỗi tháp phát một tia laser ngang sang trái. Tia của tháp $i$ được thu bởi tòa tháp đầu tiên ở bên trái có chiều cao lớn hơn $H_i$; các tháp thấp hơn không chặn tia. Nếu không có tháp như vậy, kết quả là $0$. Hãy xác định tháp thu tín hiệu của từng tháp.

Input

Dòng đầu chứa $N$. Dòng thứ hai chứa $N$ chiều cao theo thứ tự từ trái sang phải. Các chiều cao đôi một khác nhau.

Output

In $N$ số nguyên. Số thứ $i$ là chỉ số tháp thu tia từ tháp $i$, hoặc $0$ nếu tia không được tháp nào thu.

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\le5\cdot10^5$, $1\le H_i\le10^8$, các $H_i$ đôi một khác nhau.

Ví dụ

Input

5
6 9 5 7 4

Output

0 0 2 2 4

Giải thích

Các chiều cao lần lượt là $6,9,5,7,4$.

• Tháp $1$ không có tháp nào bên trái, nên in $0$.
• Tia của tháp $2$ cao $9$ đi qua tháp $1$ cao $6$ vì $6<9$ và không gặp tháp nào cao hơn ở bên trái, nên in $0$.
• Tháp $3$ cao $5$ gặp ngay tháp $2$ cao $9>5$, nên in $2$.
• Tháp $4$ cao $7$ đi qua tháp $3$ cao $5$, sau đó gặp tháp $2$ cao $9>7$, nên in $2$.
• Tháp $5$ cao $4$ gặp ngay tháp $4$ cao $7>4$, nên in $4$.

Vì vậy kết quả là 0 0 2 2 4.