Mệt mỏi vì xoáy tóc cứng đầu của mình, Nông dân John quyết định đi cắt tóc. Ông có \(N\) (\(1 \leq N \leq 10^5\)) sợi tóc xếp thành một hàng, và ban đầu sợi tóc \(i\) dài \(A_i\) micromét (\(0 \leq A_i \leq N\)). Lý tưởng nhất, ông muốn độ dài tóc không giảm từ trái sang phải, vì vậy ông định nghĩa "độ xấu" của mái tóc là số nghịch thế: số cặp \((i,j)\) sao cho \(i < j\) và \(A_i > A_j\).

Với mỗi \(j=0,1,\ldots,N-1\), FJ muốn biết độ xấu của mái tóc nếu tất cả các sợi dài hơn \(j\) đều bị cắt ngắn xuống đúng độ dài \(j\).

(Một sự thật thú vị: trung bình một người thực sự có khoảng \(10^5\) sợi tóc trên đầu!)

Dữ liệu vào

Tệp haircut.in:

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

Tệp haircut.out:

Với mỗi \(j=0,1,\ldots,N-1\), in độ xấu của mái tóc FJ trên một dòng mới.

Lưu ý rằng các số nguyên lớn xuất hiện trong bài này có thể đòi hỏi sử dụng kiểu dữ liệu số nguyên 64 bit (chẳng hạn long long trong C/C++).

Phân nhóm

• Test 2 thỏa mãn \(N \leq 100\).
• Các test 3–5 thỏa mãn \(N \leq 5000\).
• Các test 6–13 không có ràng buộc bổ sung.

Ví dụ

5
5 2 3 3 0

0
4
4
5
7

Nguồn

USACO 2020 US Open Contest, Gold — Haircut

Tác giả bài: Dhruv Rohatgi.