Cổ phiếu

Tuấn được giao nhiệm vụ theo dõi giá cổ phiếu trong \(n\) ngày liên tiếp. Ngày thứ \(i\) có giá trị \(a_i\) (\(a_i \leq 10^5\)). Một ngày được gọi là tăng trưởng nếu tồn tại ngày \(j\) trước đó (\(j < i\)) mà \(a_j < a_i\). Độ tăng trưởng của ngày \(i\) được tính là khoảng cách từ ngày \(j\) xa nhất thỏa \(a_j < a_i\) đến ngày \(i\) (bao gồm cả ngày \(j\)).

Input

Tệp COPHIEU.INP gồm:

• Dòng 1: Số nguyên \(n\) (\(1 \leq n \leq 5 \times 10^6\))
• Dòng 2: Dãy \(a_1, a_2, ..., a_n\) (\(1 \leq a_i \leq 10^5\))

Output

Tệp COPHIEU.OUT gồm một dòng chứa \(n\) số nguyên là độ tăng trưởng của các ngày tương ứng.

Example

6
10 8 5 3 9 45

0 0 0 0 3 5 

7
16 4 6 3 2 18 15

0 0 1 0 0 5 5 

Scoring

• 30% test: \(n \leq 500,000\)
• 70% test: \(500,000 < n \leq 5,000,000\)