CF538F A Heap of Heaps

安德鲁在整个学期都没有上《算法与数据结构》这门课。当他参加期末考试时，老师为了惩罚他，决定给他一个很难的题目。 老师给了安德鲁一个长度为 $n$ 的数组 $a_1, a_2, \ldots, a_n$。随后，老师要求安德鲁对于每个 $k$ 从 $1$ 到 $n-1$，都在该数组上构建一个 $k$ 叉堆，并统计有多少个元素违反了最小堆根性质，也就是元素的值小于其父节点的值。 安德鲁在维基百科上查到，$k$ 叉堆是一个以数组元素为节点的有根树。如果数组下标从 $1$ 到 $n$ 编号，则下标为 $v$ 的元素的孩子节点下标为 $k(v-1)+2, k(v-1)+3, \ldots, kv+1$（如果某些下标超出了数组范围，相应的孩子就不存在）。在任意一个 $k$ 叉堆中，除第一个元素外，每个元素都有且仅有一个父节点；第一个元素没有父节点（该元素是堆的根）。记 $p(v)$ 表示编号为 $v$ 的元素的父节点编号。对于一个非根节点 $v$，如果 $a_v < a_{p(v)}$，则称堆性质被违反。 请你帮助安德鲁完成这个任务！

第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$）。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$）。

输出一行，包含 $n-1$ 个用空格分隔的整数，第 $k$ 个数表示对于 $k=1,2,\ldots,n-1$ 时，$k$ 叉堆中有多少个元素违反了最小堆根性质。

下图给出了第一个样例的堆结构，红色标记的元素表示堆性质被违反的元素。  在第二个样例中，所有元素都相等，因此对于所有对子都满足堆性质。 由 ChatGPT 5 翻译