시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

n개의 자연수로 이루어진 수열이 하나 주어진다. (a1, a2, …, an이라고 하자.) 성관이는 이 수열을 이용해 k-ary heap들을 작성하려고 한다.

k-ary heap이란 각 internal node가 k개씩의 자식을 가지는 rooted tree를 의미한다. (단, 마지막 internal node는 k개보다 작은 자식을 가질 수도 있다.) 구체적으로 말하자면, v번 node는 k*(v-1)+2, k*(v-1)+3, …, kv + 1번 node를 자식으로 가진다. (단, 해당되는 node의 번호가 n보다 큰 경우, 그 자식은 없는 것으로 간주한다.)

성관이는 max heap의 성질을 깨뜨리는 node의 개수를 세려고 한다. 즉, root node가 아닌 어떤 노드 v의 부모 노드 p(v)에 대해, av < ap(v)라면, 이것을 max heap의 성질을 깨뜨리는 노드라고 생각한다. k = 1~n-1인 모든 경우에 대해, 이런 node의 개수를 계산하여 출력하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 자연수 n이 주어진다. (1 ≤ n ≤ 200,000)

다음 줄에는 수열을 이루는 n개의 자연수가 주어진다. (-109 ≤ ai ≤ 109)

출력

n-1개의 정수를 출력한다. i번째 수는 i-ary heap에서 max heap의 성질을 깨뜨리는 node의 개수이다.

예제 입력 1

5
1 5 4 3 2

예제 출력 1

3 2 1 0

힌트

예제를 나타내는 그림은 다음과 같다. 빨간 노드가 max heap의 성질을 위반한다.