Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#559. 树上逆序对

附加文件 统计

对于一棵有根树,定义树上的逆序对为满足 $a_i < a_{fa_i}$ 的二元对 $(i,fa_i)$ , 其中 $fa_i$ 表示结点 $i$ 的父亲结点

对于一棵 $k$ 叉树, 结点 $i$ 的子节点的编号集合为 $[1,n] \cap [k(i - 1) + 2,ki + 1]$ 中的所有整数

给定 $n$ 个结点的权值 $a_1,a_2, \dots , a_n$ , 对于 $k = 1 , 2 , \dots , n - 1$ 求出当这 $n$ 个结点构成一棵 $k$ 叉树时树上逆序对数

输入格式

第一行一个整数 $n$ , 表示结点的个数 $(2 \leq n \leq 2 \times 10^5)$

第二行包含 $n$ 个整数 $a_1,a_2, \dots , a_n$ 表示结点的权值 $(1 \leq a_i \leq 10^9)$

输出格式

输出一行 $n - 1$ 个整数分别表示 $k = 1 , 2 , \dots , n - 1$ 时树上逆序对数

样例输入

5
5 4 5 4 3

样例输出

3 2 3 3