Nhiệt độ hằng ngày (Daily Temperatures)

Nguồn: LeetCode

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

Đề bài

Cho dãy temperatures, trong đó phần tử thứ $i$ là nhiệt độ của ngày $i$. Với mỗi ngày, hãy tính số ngày phải chờ để gặp một ngày có nhiệt độ cao hơn. Nếu về sau không có ngày nào nóng hơn, kết quả là $0$.

Input

Dòng đầu chứa $n$, số ngày. Dòng thứ hai chứa $n$ nhiệt độ.

Output

In $n$ số nguyên, trong đó số thứ $i$ là số ngày cần chờ từ ngày $i$ đến ngày nóng hơn tiếp theo, hoặc $0$.

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^5$, $30\le temperatures_i\le100$.

Ví dụ

Input

8
73 74 75 71 69 72 76 73

Output

1 1 4 2 1 1 0 0

Giải thích

Các nhiệt độ theo ngày là $73,74,75,71,69,72,76,73$.

• Ngày $1$ có $73$; ngày $2$ có $74>73$, nên chờ $1$ ngày.
• Ngày $2$ có $74$; ngày $3$ có $75>74$, nên chờ $1$ ngày.
• Ngày $3$ có $75$; các ngày $4,5,6$ lần lượt là $71,69,72$ đều không cao hơn $75$; ngày $7$ có $76>75$, nên chờ $7-3=4$ ngày.
• Ngày $4$ có $71$; ngày $5$ là $69$, còn ngày $6$ là $72>71$, nên chờ $2$ ngày.
• Ngày $5$ có $69$; ngày $6$ là $72>69$, nên chờ $1$ ngày.
• Ngày $6$ có $72$; ngày $7$ là $76>72$, nên chờ $1$ ngày.
• Ngày $7$ có $76$ và không có ngày nào sau đó nóng hơn, nên nhận $0$.
• Ngày $8$ là ngày cuối, nên nhận $0$.

Vì vậy output là 1 1 4 2 1 1 0 0.