一個跑步俱樂部正在招募新成員並快速發展，每日恰好有一位新成員加入。每位成員加入時都有一個特定嘅初始實力水平，並根據佢哋到步嘅順序分配一個唯一嘅 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]$。