Các tòa nhà (Buildings)

Nguồn: AtCoder

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

Đề bài

Có $N$ tòa nhà đánh số từ $1$ đến $N$, tòa $i$ cao $H_i$. Các chiều cao đôi một khác nhau. Với mỗi $i$, hãy đếm số chỉ số $j>i$ sao cho giữa $i$ và $j$ không có tòa nào cao hơn tòa $j$.

Input

Dòng đầu chứa $N$. Dòng thứ hai chứa $N$ số nguyên $H_1,H_2,\ldots,H_N$.

Output

In $N$ số nguyên; số thứ $i$ là số tòa $j$ thỏa điều kiện đối với tòa $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\le2\cdot10^5$, $1\le H_i\le N$, các $H_i$ đôi một khác nhau.

Ví dụ

Input

5
2 1 4 3 5

Output

3 2 2 1 0

Giải thích

Dãy chiều cao là $2,1,4,3,5$.

• Với $i=1$, các chỉ số $j=2,3,5$ thỏa điều kiện. $j=4$ không thỏa vì tòa $3$ cao $4$ nằm giữa và cao hơn tòa $4$ cao $3$. Vì vậy $c_1=3$.
• Với $i=2$, $j=3$ và $j=5$ thỏa điều kiện, còn $j=4$ bị tòa $3$ cao hơn che theo điều kiện của đề. Do đó $c_2=2$.
• Với $i=3$, cả $j=4$ và $j=5$ đều thỏa, nên $c_3=2$.
• Với $i=4$, chỉ có $j=5$, nên $c_4=1$.
• Với $i=5$, không còn tòa nào bên phải, nên $c_5=0$.

Do đó chương trình in 3 2 2 1 0.