힙들의 힙

n개의 정수로 이루어진 수열 $a_1, a_2, \dots, a_n$이 주어진다. 이 수열을 그대로 k진 힙의 노드 값으로 놓고, 최소 힙 성질을 깨뜨리는 노드가 몇 개인지 센다.

k진 힙은 내부 노드가 자식을 최대 k개까지 가지는 루트 있는 트리다. 노드 번호는 1번부터 n번까지이고 1번이 루트다. v번 노드는 $k(v-1)+2$번, $k(v-1)+3$번, $\dots$, $kv+1$번 노드를 자식으로 가진다. 번호가 n보다 큰 자식은 없는 것으로 본다. 그래서 마지막 내부 노드만 자식을 k개보다 적게 가질 수 있다.

루트가 아닌 노드 v의 부모를 $p(v)$라 하자. $a_v < a_{p(v)}$이면 v는 최소 힙 성질을 깨뜨리는 노드다. $k = 1, 2, \dots, n-1$ 각각에 대해 이런 노드가 몇 개인지 구하시오.

첫째 줄에 정수 n이 주어진다. ($1 \le n \le 200000$)

둘째 줄에 수열을 이루는 n개의 정수 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다. ($-10^9 \le a_i \le 10^9$)

$n-1$개의 정수를 한 줄에 공백 하나로 구분해 출력한다. $i$번째 수는 $i$진 힙에서 최소 힙 성질을 깨뜨리는 노드의 개수다. $n = 1$이면 해당하는 k가 없으므로 아무것도 출력하지 않는다.

아래 그림은 $n = 5$이고 수열이 $1\ 5\ 4\ 3\ 2$일 때 $k = 1, 2, 3, 4$인 힙이다. 빨간 노드가 최소 힙 성질을 깨뜨린다.