样例下载

题目描述

$N$ 棵树排成一排，第 $i$ 棵树的高度为 $H_i (0 ≤ H_i ≤ N)$。注意：可能有的树高度为 0.

树的高度参差不齐，显得并不美观。这里定义这排树的参差度为高度序列中含有的逆序对的数目。

现在要对一些树进行剪枝，降低他们的高度。

请你计算：对于每一个 $j (0 ≤ j ≤ N-1)$，所有高度大于 $j$ 的树的高度均降低到 $j$ 时这排树的参差度。

输入格式

第一行：一个整数 $N$。

第二行：$N$ 个整数，依次为 $H_1,H_2,……,H_N$。

输出格式

共 $N$ 行：每行一个整数，依次表示对于每一个 $j (0 ≤ j ≤ N-1)$，所有高度大于 $j$ 的树的高度均降低到 $j$ 时这排树的参差度。

样例输入

5
5 2 3 3 0

样例输出

0
4
4
5
7

数据范围

大约 $15\%$ 的数据满足 $N ≤ 100$。

大约 $25\%$ 的数据满足 $N ≤ 5000$。

$100\%$ 的数据，$1 ≤ N ≤ 10^5$，$0 ≤ H_i ≤ N$