Inversions on a Tree

Problem Description

For a rooted tree, define an inversion on the tree as an ordered pair $(i, fa_i)$ satisfying $a_i < a_{fa_i}$, where $fa_i$ denotes the parent of node $i$.

For a $k$-ary tree, the set of child indices of node $i$ is exactly all integers in $[1, n] \cap [k(i-1)+2, ki+1]$.

Given the weights $a_1, a_2, \dots, a_n$ of $n$ nodes, for each $k = 1, 2, \dots, n-1$ compute the number of inversions on the tree when these $n$ nodes form a $k$-ary tree.

Input Format

The first line contains an integer $n$, the number of nodes ($2 \le n \le 2 \times 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, the node weights ($1 \le a_i \le 10^9$).

Output Format

Output one line with $n-1$ integers, the numbers of inversions for $k = 1, 2, \dots, n-1$ respectively.

Sample Input

5
5 4 5 4 3

Sample Output

3 2 3 3