题目背景

「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 }- $$

题目描述

给定 $1\sim n$ 的排列 $a_{[1,n]}$。

请对于每一个 $i$，考虑如下操作序列：

1. 首先在 $[1,i]$ 中选取一个子序列（可以为空）；
2. 然后将这个子序列内的数重新排列。

求出 所有不同的操作序列产生的排列 的逆序对数总和是多少，答案模 $20051131$。

两个操作序列不同当且仅当选取的子序列不同或重新排列的方式不同。

操作不会真正被执行到排列上。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个数，表示排列 $a$。

输出格式

$n$ 行，每行一个数，表示对于前缀 $[1,i]$ 所有不同的操作序列产生的排列的逆序对数总和模 $20051131$ 的值。

3
1 2 3

0
1
14

8
3 2 4 1 6 8 7 5

16
39
132
476
2842
21137
172002
1427424

提示

样例 1 解释：

• 对于 $[1,1]$，无法产生逆序对，答案为 $0$。
• 对于 $[1,2]$，只有一种操作序列可以产生 $2,1,3$，答案为 $1$。
• 对于 $[1,3]$：
  • 有 $8$ 种操作序列产生 $1,2,3$；
  • 有 $2$ 种操作序列产生 $1,3,2$；
  • 有 $2$ 种操作序列产生 $2,1,3$；
  • 有 $1$ 种操作序列产生 $2,3,1$；
  • 有 $1$ 种操作序列产生 $3,1,2$；
  • 有 $2$ 种操作序列产生 $3,2,1$；
• 答案为 $0\times 8+1\times 2+1\times 2+2\times 1+2\times 1+2\times 3=14$。

样例 2 解释：

• 对于 $i=1$，只有两种操作序列，产生的排列都有 $8$ 个逆序对，故答案是 $16$。
• 对于 $i=2$，有 $4$ 种操作序列产生 $3, 2, 4, 1, 6, 8, 7, 5$，有 $1$ 种操作序列产生 $2,3,4,1,6,8,7,5$，答案为 $8\times 4+7\times 1=39$。

数据范围：

• 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%）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n\leq 10^6$。

idea：Sol1，solution：Sol1，code：Sol1，data：Sol1