Một câu lạc bộ chạy bộ đang tuyển thành viên và phát triển nhanh chóng, với đúng một thành viên mới tham gia mỗi ngày. Mỗi thành viên khi vào đều có một mức kỹ năng ban đầu cụ thể và được gán một ID duy nhất dựa trên thứ tự gia nhập.

Vào cuối mỗi ngày, Huấn luyện viên thích tính một chỉ số mà ông gọi là "tổng tiềm năng" của câu lạc bộ. Giá trị này đơn giản là tổng tiềm năng cá nhân của tất cả các thành viên hiện tại. Để giữ cho các thành viên có động lực, tiềm năng của một thành viên được tính thông qua một kịch bản giả định "nếu như" liên quan đến một buổi tập luyện cường độ cao duy nhất.

Trong buổi tập tưởng tượng này, một thành viên có thể chọn bỏ ra một lượng nỗ lực nhất định để tạm thời nâng cao mức kỹ năng của mình. Với mỗi $1$ đơn vị nỗ lực bỏ ra, mức kỹ năng của họ tăng thêm đúng $1$ đơn vị. Đổi lại, họ nhận được $1$ đơn vị "hạnh phúc" cho mỗi thành viên khác hiện có trong câu lạc bộ thỏa mãn:

• gia nhập câu lạc bộ muộn hơn hẳn so với họ; và
• ban đầu có kỹ năng cao hơn hẳn so với họ, nhưng hiện đã bị bắt kịp hoặc vượt qua nhờ buổi tập luyện.

Lưu ý rằng trong quá trình tính toán này, chỉ mức kỹ năng của thành viên đó được tăng lên, trong khi mức kỹ năng của tất cả các thành viên khác vẫn giữ nguyên ở giá trị ban đầu.

Tiềm năng của một thành viên được định nghĩa là giá trị lớn nhất có thể của lợi ích ròng (hạnh phúc trừ đi nỗ lực) mà họ có thể đạt được bằng cách chọn mức nỗ lực tối ưu. Những buổi tập này hoàn toàn mang tính lý thuyết; chúng chỉ được dùng cho báo cáo hàng ngày của Huấn luyện viên, và mức kỹ năng thực tế của các thành viên vẫn không đổi qua từng ngày.

Nhiệm vụ của bạn là giúp Huấn luyện viên tính tổng tiềm năng của câu lạc bộ vào cuối mỗi ngày trong đợt tuyển thành viên.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$), biểu thị số ngày câu lạc bộ tuyển thành viên.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), trong đó $a_i$ là mức kỹ năng ban đầu của thành viên gia nhập vào ngày $i$.

Kết quả

In ra $n$ số nguyên trên một dòng duy nhất. Số nguyên thứ $k$ là tổng tiềm năng của câu lạc bộ vào cuối ngày $k$.

Ví dụ

Dữ liệu vào 1

8
1 2 3 1 2 3 2 3

Kết quả 1

0 0 0 0 1 3 5 9

Dữ liệu vào 2

1
1

Kết quả 2

0

Giải thích

Giải thích Ví dụ 1: Vào ngày $5$, có $5$ thành viên với mức kỹ năng $[1, 2, 3, 1, 2]$. Đối với thành viên $1$: Có $3$ thành viên gia nhập muộn hơn với kỹ năng cao hơn hẳn: thành viên $2$, thành viên $3$ và thành viên $5$. Tiềm năng tối đa của thành viên $1$ là $1$, đạt được bằng một trong hai chiến lược sau:

• Nếu thành viên $1$ bỏ ra $1$ đơn vị nỗ lực, kỹ năng của họ trở thành $2$. Họ sẽ bắt kịp hoặc vượt qua thành viên $2$ và thành viên $5$. Hạnh phúc là $2$ đơn vị, và lợi ích ròng là $2 - 1 = 1$ đơn vị.
• Nếu thành viên $1$ bỏ ra $2$ đơn vị nỗ lực, kỹ năng của họ trở thành $3$. Họ sẽ bắt kịp hoặc vượt qua các thành viên $2$, $3$ và $5$. Hạnh phúc là $3$ đơn vị, và lợi ích ròng là $3 - 2 = 1$ đơn vị.

Các thành viên khác có tiềm năng tối đa là $0$. Do đó, tổng tiềm năng vào ngày $5$ là $1$.

Vào ngày $8$, có $8$ thành viên với mức kỹ năng $[1, 2, 3, 1, 2, 3, 2, 3]$. Các mức nỗ lực tối ưu là $[2, 1, 0, 2, 1, 0, 1, 0]$ và các tiềm năng tối đa tương ứng là $[4, 2, 0, 2, 1, 0, 0, 0]$.