12990번 - A Heap of Heaps

n개의 자연수로 이루어진 수열이 하나 주어진다. (a₁, a₂, …, a_n이라고 하자.) 성관이는 이 수열을 이용해 k진 힙을 작성하려고 한다.

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

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

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

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

n-1개의 정수를 출력한다. i번째 수는 i진 힙에서 최소 힙의 성질을 깨뜨리는 노드의 개수이다.

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