I. Inversion Counting
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a permutation $$$a$$$ from $$$1$$$ to $$$n$$$, an inversion is defined as a pair of indices $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$ and $$$a_i \gt a_j$$$.

Counting the total number of inversions is an extremely classic problem. In this problem, we consider a variation.

For each $$$k$$$ from $$$1$$$ to $$$n-1$$$, find the number of pairs $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$, $$$j - i = k$$$, and $$$a_i \gt a_j$$$.

Input

The first line contains a single integer $$$n$$$, representing the length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, representing the permutation.

  • $$$2 \le n \le 2.5 \times 10^5$$$
  • $$$a_1, a_2, \ldots, a_n$$$ is a permutation from $$$1$$$ to $$$n$$$.
Output

Output $$$n-1$$$ space-separated integers on a single line. The $$$k$$$-th integer should represent the number of pairs $$$(i, j)$$$ satisfying the conditions for the given value of $$$k$$$.

Examples
Input
5
3 1 4 5 2
Output
2 1 0 1
Input
6
6 5 4 3 2 1
Output
5 4 3 2 1