← 返回题目列表

Codeforces · 538/F

F. 一堆堆

中文机器翻译题面 查看原题

Andrew 整个学期都跳过了“算法和数据结构”主题的课程。当他期末考试时,老师决定给他一项艰巨的任务作为惩罚。

老师给了 Andrew 一个由 n 个数字组成的数组 a1, ..., an。之后,他要求 Andrew 对从 1 到 n - 1 的每个 k 在数组上构建一个 k 元堆,并计算违反最小根堆属性的元素的数量,即某个元素的值小于其父元素的值。

Andrew 在维基百科上查找到 k 元堆是一个有根树,其顶点位于数组的元素中。如果数组的元素索引从 1 到 n,则元素 v 的子元素是索引为 k(v - 1) + 2, ..., kv + 1 的元素(如果其中一些元素位于数组边界之外,则相应的子元素不存在)。在任何 k 元堆中,除了第一个元素之外的每个元素都只有一个父元素;对于元素 1,父元素不存在(该元素是堆的根)。将 p(v) 表示为带有数字 v 的元素的父元素的编号。假设对于非根元素 v,如果 av < ap(v),则违反了堆的属性。

帮助安德鲁应对任务!

输入

第一行包含一个整数 n (2 ≤ n ≤ 2·105)。

第二行包含 n 个空格分隔的整数 a1, ..., an ( - 109 ≤ ai ≤ 109)。

输出

在单行中打印 n - 1 个整数,用一个空格分隔连续的数字 - 违反 k 元堆属性的元素数量,对于 k = 1, 2, ..., n - 1。

示例

输入 #1

5
1 5 4 3 2

输出 #1

3 2 1 0

输入 #2

6
2 2 2 2 2 2

输出 #2

0 0 0 0 0

注意

第一个样本的堆图片如下;违反堆属性的元素用红色标记。

在第二个示例中,所有元素都相等,因此该属性适用于所有对。