CF538F.A Heap of Heaps

Andrew skipped lessons on the subject 'Algorithms and Data Structures' for the entire term. When he came to the final test, the teacher decided to give him a difficult task as a punishment.

The teacher gave Andrew an array of n numbers _a_1, ..., a__n. After that he asked Andrew for each k from 1 to n - 1 to build a k-ary heap on the array and count the number of elements for which the property of the minimum-rooted heap is violated, i.e. the value of an element is less than the value of its parent.

Andrew looked up on the Wikipedia that a k-ary heap is a rooted tree with vertices in elements of the array. If the elements of the array are indexed from 1 to n, then the children of element v are elements with indices k(v - 1) + 2, ..., kv + 1 (if some of these elements lie outside the borders of the array, the corresponding children are absent). In any k-ary heap every element except for the first one has exactly one parent; for the element 1 the parent is absent (this element is the root of the heap). Denote p(v) as the number of the parent of the element with the number v. Let's say that for a non-root element v the property of the heap is violated if a__v < a__p(v).

Help Andrew cope with the task!

安德鲁整个学期都逃掉了“算法与数据结构”这门课。当他参加期末考试时，老师决定给他一道难题作为惩罚。

老师给了安德鲁一个包含 $n$ 个数的数组 $a_1, \dots, a_n$。接着，老师要求安德鲁对每个 $k$（从 $1$ 到 $n-1$）在该数组上构建一个 $k$-叉堆，并统计其中违反最小根堆性质的元素个数，即：某个元素的值小于其父节点的值。

安德鲁查阅了维基百科，了解到：一个 $k$-叉堆是一棵以数组元素为顶点的有根树。若数组元素的下标从 $1$ 编号至 $n$，则元素 $v$ 的子节点对应数组中下标为 $k(v - 1) + 2,\ \dots,\ kv + 1$ 的那些元素（若这些下标超出了数组边界，则相应子节点不存在）。在任意 $k$-叉堆中，除第一个元素外，每个元素恰好有一个父节点；而元素 $1$ 没有父节点（该元素即为堆的根）。记 $p(v)$ 为元素 $v$ 的父节点的下标。我们称：对任意非根元素 $v$，若 $a_v < a_{p(v)}$，则该元素违反堆性质。

请帮助安德鲁完成这项任务！

The first line contains a single integer n (2 ≤ n ≤ 2·105).

The second line contains n space-separated integers _a_1, ..., a__n ( - 109 ≤ a__i ≤ 109).

第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）。

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

in a single line print n - 1 integers, separate the consecutive numbers with a single space — the number of elements for which the property of the k-ary heap is violated, for k = 1, 2, ..., n - 1.

在一行中输出 $n-1$ 个整数，用单个空格分隔相邻数字——即对 $k = 1, 2, \dots, n-1$，满足 $k$ 叉堆性质被违反的元素个数。

Pictures with the heaps for the first sample are given below; elements for which the property of the heap is violated are marked with red.

In the second sample all elements are equal, so the property holds for all pairs.

第一个样例对应的堆结构图如下所示；其中违反堆性质的元素用红色标记。

在第二个样例中，所有元素均相等，因此该性质对所有元素对均成立。