Cổ phiếu

Tuấn được công ty giao cho nhiệm vụ theo dõi giá trị cổ phiếu của công ty mình đang làm việc.

Tuấn theo dõi giá trị cổ phiếu trong \(n\) ngày, ngày thứ \(i\) có giá trị cổ phiếu là \(a_i\).

Ngày thứ \(i\) được gọi là tăng trưởng nếu tồn tại một ngày \(j\) trước đó (\(j < i\)) có giá trị cổ phiếu thấp hơn, tức là \(a_j < a_i\).

Độ tăng trưởng của ngày thứ \(i\) được tính bằng \(i - j\), trong đó \(j\) là ngày đứng trước xa nhất (chỉ số nhỏ nhất) có giá trị cổ phiếu thấp hơn ngày thứ \(i\). Nếu không tồn tại ngày \(j\) như vậy thì độ tăng trưởng của ngày thứ \(i\) bằng \(0\).

Yêu cầu. Tính độ tăng trưởng của mỗi ngày trong các ngày Tuấn đang theo dõi.

Input

• Dòng đầu ghi số nguyên dương \(n\) (\(n \le 10^6\));

• Dòng thứ hai ghi dãy số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^5\)).

Output

Ghi ra một dòng gồm \(n\) giá trị là độ tăng trưởng của các ngày theo dõi tương ứng, các số cách nhau bởi một dấu cách.

Notes

• Ở ngày thứ \(5\), giá trị là \(9\). Ngày đứng trước xa nhất có giá trị nhỏ hơn là ngày thứ \(2\) có giá trị \(8\), nên độ tăng trưởng là \(5 - 2 = 3\).

• Ở ngày thứ \(7\), giá trị là \(15\). Ngày đứng trước xa nhất có giá trị nhỏ hơn cũng là ngày thứ \(2\), nên độ tăng trưởng là \(7 - 2 = 5\).

Scoring

• (\(30\%\)) \(0 < n \le 5 \cdot 10^5\);

• (\(70\%\)) \(5 \cdot 10^5 < n \le 10^6\).