一個跑步俱樂部正在招募新成員並快速發展，每天恰好有一名新成員加入。每位成員加入時都有一個特定的初始實力水準，並根據他們的到來順序被分配一個唯一的 ID。

在每天結束時，教練喜歡計算一個他稱為俱樂部「總潛力」的指標。這個值就是當前所有成員個人潛力的總和。為了保持成員們的積極性，成員的潛力是透過一個涉及單次高強度訓練的假設性「如果……會怎樣」場景來計算的。

在這個虛構的訓練中，成員可以選擇付出一定量的努力來暫時提升自己的實力水準。他們每付出 $1$ 單位的努力，其實力水準就會恰好提升 $1$ 單位。作為回報，對於當前俱樂部中滿足以下條件的每一位其他成員，他們將獲得 $1$ 單位的「快樂值」：

• 加入俱樂部的時間嚴格晚於他們；且
• 原本的實力水準嚴格高於他們，但由於這次訓練，現在被他們追平或超越。

注意，在此計算過程中，只有該成員的實力水準會提升，而所有其他成員的實力水準仍保持在原始值不變。

單個成員的潛力定義為：透過最優地選擇努力程度，他們所能獲得的淨收益（快樂值減去努力值）的最大可能值。這些訓練完全是理論上的；它們僅用於教練的每日報告，成員們實際的實力水準日復一日保持不變。

你的任務是幫助教練計算在招募期的每一天結束時俱樂部的總潛力。

輸入格式

輸入的第一行包含一個整數 $n$ ($1 \le n \le 10^5$)，表示俱樂部招募成員的天數。

第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，其中 $a_i$ 表示在第 $i$ 天加入的成員的初始實力水準。

輸出格式

在單行中輸出 $n$ 個整數。第 $k$ 個整數應當是第 $k$ 天結束時俱樂部的總潛力。

範例

輸入 1

8
1 2 3 1 2 3 2 3

輸出 1

0 0 0 0 1 3 5 9

輸入 2

1
1

輸出 2

0

說明

範例 1 說明：在第 $5$ 天，有 $5$ 名成員，其實力水準為 $[1, 2, 3, 1, 2]$。對於成員 $1$： 有 $3$ 名較晚加入且實力嚴格高於他的成員：成員 $2$、成員 $3$ 和成員 $5$。成員 $1$ 的最大潛力為 $1$，可以透過以下任一策略達到：

• 如果成員 $1$ 付出 $1$ 單位的努力，他的實力將變為 $2$。他將追平或超越成員 $2$ 和成員 $5$。快樂值為 $2$ 單位，淨收益為 $2 - 1 = 1$ 單位。
• 如果成員 $1$ 付出 $2$ 單位的努力，他的實力將變為 $3$。他將追平或超越成員 $2$、$3$ 和 $5$。快樂值為 $3$ 單位，淨收益為 $3 - 2 = 1$ 單位。

其他成員的最大潛力均為 $0$。因此，第 $5$ 天的總潛力為 $1$。

在第 $8$ 天，有 $8$ 名成員，其實力水準為 $[1, 2, 3, 1, 2, 3, 2, 3]$。最優努力值為 $[2, 1, 0, 2, 1, 0, 1, 0]$，對應的最大潛力分別為 $[4, 2, 0, 2, 1, 0, 0, 0]$。