题目描述

给定一个长度为 $n$ 的整数数组 $A$。

对于每个整数 $j$（$0 \le j < n$），分别进行一次如下操作：将数组中所有大于 $j$ 的数都改为 $j$，其余数保持不变。每次操作都从最初给定的数组开始，互不影响。

如果 $1 \le x<y \le n$ 且 $A_x>A_y$，则称 $(x,y)$ 是一个逆序对。

请依次求出 $j=0,1,\ldots,n-1$ 时，操作完成后的数组中有多少个逆序对。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$。

输出格式

输出 $n$ 行。第 $j+1$ 行输出当上限为 $j$ 时，操作完成后的数组中的逆序对数量。

样例

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$