あるランニングクラブは部員を募集して急成長しており、毎日ちょうど 1 人の新入部員が加入します。各部員は固有の初期スキルレベルを持っており、加入した順番に基づいて一意の ID が割り当てられます。

毎日の終わりに、コーチはクラブの「総ポテンシャル」と呼ぶ指標を計算するのが好きです。この値は、現在所属しているすべての部員の個人ポテンシャルの総和です。部員のモチベーションを保つため、部員のポテンシャルは、1 回の激しいトレーニングを行うという「もしも」の仮定シナリオを通じて計算されます。

この仮想のトレーニングでは、部員はある程度の努力を払って自分のスキルレベルを一時的に引き上げることができます。努力を $1$ 単位払うごとに、スキルレベルはちょうど $1$ 単位増加します。その見返りとして、現在クラブに所属している他の部員のうち、以下の条件を両方満たす部員 1 人につき $1$ 単位の「幸福度」を得ます：

• 自分よりも厳密に後にクラブに加入した。
• もともとは自分よりも厳密に高いスキルレベルを持っていたが、トレーニングのおかげで追いつかれたか追い越された。

この計算の間、その部員のスキルレベルのみが増加し、他のすべての部員のスキルレベルは元の値のまま固定されることに注意してください。

1 人の部員のポテンシャルは、努力量を最適に選ぶことで達成できる純利益（幸福度から努力量を引いたもの）の最大可能値として定義されます。これらのトレーニングは完全に理論上のものであり、コーチの日報のためにのみ使用され、部員の実際のスキルレベルは日々変化しません。

あなたの仕事は、募集期間の各日の終わりにおけるクラブの総ポテンシャルをコーチが計算するのを手伝うことです。

入力

入力の 1 行目には、クラブが部員を募集する日数を表す整数 $n$ ($1 \le n \le 10^5$) が与えられます。

2 行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が与えられます。ここで $a_i$ は $i$ 日目に加入する部員の初期スキルレベルです。

出力

1 行に $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$ 日目には、スキルレベルが $[1, 2, 3, 1, 2]$ の $5$ 人の部員がいます。部員 $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$ 日目には、スキルレベルが $[1, 2, 3, 1, 2, 3, 2, 3]$ の $8$ 人の部員がいます。最適な努力量は $[2, 1, 0, 2, 1, 0, 1, 0]$ であり、対応する最大ポテンシャルは $[4, 2, 0, 2, 1, 0, 0, 0]$ です。