Description

You are given a permutation $a_{[1,n]}$ of $1 \sim n$.

For each $i$, consider the following sequence of operations:

1. First, choose a subsequence in $[1,i]$ (it can be empty).
2. Then, reorder the numbers in this subsequence.

Compute the total sum of inversion counts of all permutations produced by all different operation sequences, modulo $20051131$.

Two operation sequences are different if and only if the chosen subsequence is different, or the reordering method is different.

The operations will not actually be applied to the permutation.

Input Format

The first line contains an integer $n$.

The next line contains $n$ numbers, representing the permutation $a$.

Output Format

Output $n$ lines, one number per line, representing the value (modulo $20051131$) of the total sum of inversion counts of all permutations produced by all different operation sequences for the prefix $[1,i]$.

3
1 2 3

0
1
14

8
3 2 4 1 6 8 7 5

16
39
132
476
2842
21137
172002
1427424

Hint

Explanation for Sample 1:

• For $[1,1]$, no inversions can be produced, so the answer is $0$.
• For $[1,2]$, only one operation sequence can produce $2,1,3$, so the answer is $1$.
• For $[1,3]$:
  • There are $8$ operation sequences that produce $1,2,3$.
  • There are $2$ operation sequences that produce $1,3,2$.
  • There are $2$ operation sequences that produce $2,1,3$.
  • There is $1$ operation sequence that produces $2,3,1$.
  • There is $1$ operation sequence that produces $3,1,2$.
  • There are $2$ operation sequences that produce $3,2,1$.
• The answer is $0\times 8+1\times 2+1\times 2+2\times 1+2\times 1+2\times 3=14$.

Explanation for Sample 2:

• For $i=1$, there are only two operation sequences, and the permutations produced both have $8$ inversions, so the answer is $16$.
• For $i=2$, there are $4$ operation sequences that produce $3, 2, 4, 1, 6, 8, 7, 5$, and $1$ operation sequence that produces $2,3,4,1,6,8,7,5$. The answer is $8\times 4+7\times 1=39$.

Constraints:

• Subtask 1 (10%): $n\leq 8$.
• Subtask 2 (20%): $n\leq 50$.
• Subtask 3 (20%): $n\leq 300$.
• Subtask 4 (20%): $n\leq 3\times 10^3$.
• Subtask 5 (30%): no special constraints.

For $100\%$ of the testdata, $1\leq n\leq 10^6$.

idea: Sol1, solution: Sol1, code: Sol1, data: Sol1

Translated by ChatGPT 5