题目描述

有 $N$ 个整数，第 $i$ 个整数的值 $A_i$ 满足 $0 \le A_i \le N$。

现有 $N$ 次减数操作，第 $j$ 次（$j \in [0, N-1]$）减数操作要求将这组数中所有满足 $A_i > j$ 的数，减少到 $j$，并统计出此时这组数中逆序对的总数。

逆序对指的是，如果有两个整数 $A_i$ 和 $A_j$，满足 $i < j$ 且 $A_i > A_j$，则这两个整数构成逆序对。

请注意：这里的每次操作都是在原始 $N$ 个数的基础上进行减数操作。即：在第 $j$ 次操作之后，第 $j+1$ 次操作之前，数组中的每个数的值会恢复为读入的值。

输入格式

第 $1$ 行输入整数 $N$。

第 $2$ 行输入 $N$ 个整数 $A_1, …, A_n$。

输出格式

输出 $N$ 行，分别代表对于 $j = 0, 1, …, N-1$ 的情况下，进行减数操作后逆序对的数量。

样例

输入

5
5 3 2 4 0

输出

0
4
4
6
7

数据范围

对于 $20\%$ 的数据，满足 $1 \le N \le 100$。

对于 $50\%$ 的数据，满足 $1 \le N \le 5000$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$0 \le A_i \le N$。