Hàng đợi (Queue)

Nguồn: Codeforces

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

Đề bài

Có $n$ người đứng theo thứ tự từ trái sang phải, người $i$ có giá trị $a_i$. Với mỗi $i$, hãy tìm vị trí $j>i$ xa nhất về bên phải sao cho $a_j<a_i$. Nếu tồn tại, cần in số người đứng giữa $i$ và $j$, tức $j-i-1$; nếu không có vị trí như vậy, in $-1$.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In $n$ số nguyên theo thứ tự các vị trí.

Subtask

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

Ví dụ

Input

6
10 8 5 3 50 45

Output

2 1 0 -1 0 -1

Giải thích

Các giá trị lần lượt là $10,8,5,3,50,45$.

• Vị trí $1$ có giá trị $10$. Vị trí xa nhất bên phải có giá trị nhỏ hơn $10$ là vị trí $4$ với giá trị $3$. Có hai vị trí $2,3$ nằm giữa, nên kết quả là $2$.
• Vị trí $2$ có giá trị $8$. Vị trí xa nhất nhỏ hơn $8$ vẫn là vị trí $4$; chỉ có vị trí $3$ ở giữa, nên kết quả là $1$.
• Vị trí $3$ có giá trị $5$. Vị trí $4$ có giá trị $3<5$ và không còn vị trí nhỏ hơn nào xa hơn, nên số người ở giữa là $0$.
• Vị trí $4$ có giá trị $3$. Không có giá trị nhỏ hơn ở bên phải, nên kết quả là $-1$.
• Vị trí $5$ có giá trị $50$. Vị trí $6$ có giá trị $45<50$, hai vị trí kề nhau nên kết quả là $0$.
• Vị trí $6$ không có ai ở bên phải, nên kết quả là $-1$.

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