一个跑步俱乐部正在招募新成员并快速发展，每天恰好有一名新成员加入。每位成员加入时都有一个特定的初始实力水平，并根据他们的到来顺序被分配一个唯一的 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]$。