Xếp hộp

Bé Na có một dãy gồm \(N\) hộp xếp thành hàng ngang, trong đó hộp thứ \(i\) chứa \(A_i\) viên bi (\(0 \leq A_i \leq N\)).

Na thích những dãy hộp mà số bi trong các hộp tăng dần từ trái sang phải. Vì vậy, Na định nghĩa một chỉ số gọi là "độ rối" của dãy hộp: đó là số cặp \((i,j)\) sao cho \(i < j\) nhưng \(A_i > A_j\).

Bây giờ, Na thử một trò chơi: với mỗi giá trị \(j = 0,1,2,\dots,N-1\), Na sẽ giới hạn lại số bi trong các hộp. Cụ thể, những hộp nào đang có nhiều hơn \(j\) viên bi sẽ được giảm xuống còn đúng \(j\) viên. Sau đó, Na muốn biết độ rối của dãy hộp khi áp dụng quy tắc trên.

Với mỗi \(j = 0,1,\dots,N-1\), hãy tính và in ra độ rối của dãy hộp sau khi áp dụng thao tác giới hạn với giá trị \(j\)

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \leq N \leq 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \leq A_i \leq N\)).

Output

• In ra \(N\) dòng, dòng thứ \(j+1\) chứa độ rối của dãy khi sử dụng giá trị \(j\).

Example

5
5 2 3 3 0

0
4
4
5
7

Scoring

• Có \(30\%\) số điểm thỏa mãn \(N \leq 100\).
• Có \(30\%\) số điểm thỏa mãn \(N \leq 5000\).
• Có \(40\%\) số điểm không có ràng buộc gì thêm.