Minimum Inversion Subsequence Counts

You are given a permutation \(a_{1..n}\) of the integers \(1, 2, \dots, n\). Note that there are \(2^n - 1\) non-empty subsequences of this permutation.

For every integer \(k\) with \(1 \le k \le n\), your task is to choose a subsequence of length \(k\) whose number of inversion pairs is minimized, and then output the number of subsequences (of length \(k\)) that achieve this minimum inversion count.

An inversion pair in a sequence \(b_1, b_2, \dots, b_k\) is defined as a pair of indices \((i,j)\) with \(1 \le i b_j\). If an increasing subsequence exists then its inversion count is \(0\). Note that for some values of \(k\) it might be impossible to have an inversion count of \(0\) if no increasing subsequence of that length exists.

Input/Output Example: For instance, if \(n = 3\) and the permutation is 2 3 1, then:

• For \(k = 1\): All one-element subsequences have \(0\) inversions. There are 3 such subsequences.
• For \(k = 2\): The subsequences are [2,3] (0 inversions), [2,1] (1 inversion) and [3,1] (1 inversion). The minimum inversion count is \(0\) and only [2,3] attains that.
• For \(k = 3\): The only subsequence [2,3,1] has 1 inversion. So answer is 1.

The required output for this example is:

3 1 1

inputFormat

The first line contains a single integer \(n\) (the size of the permutation).

The second line contains \(n\) distinct integers \(a_1, a_2, \dots, a_n\) which form a permutation of \(1, 2, \dots, n\) separated by spaces.

outputFormat

Output \(n\) integers in one line separated by spaces. The \(k\)-th integer represents the number of subsequences of length \(k\) that achieve the minimum possible inversion count among all subsequences of that length.

Note: There is no modulo required.

sample

3
1 2 3

3 3 1