P7781 "MCOI-Zero / AC6-M07" Selumna Peak

"Now that's what I call squadron!" "Come on, it's payback time." **"Gracemeria is dead ahead!!"** $$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 07} \\\Large\text{Selumna Peak}\\\tiny-\textit{ Shimmering Death }-$$ 

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.

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

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]$.

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