题目描述

对任意一个整数 $x$，循环步进操作是指将 $x$ 变成 $(x+1)\bmod M$，其中 $M$ 是一个给定的上限。

给定 $N$ 个数字组成的一个序列 $A_0,A_1,A_2,\dots, A_{N-1}$。

请先输出序列的逆序对数量，然后对序列里的每个数字进行一次循环步进操作。然后将上述流程重复执行 $M$ 遍。

所谓一组逆序对，是指序列中出现了两个元素，其大小与其顺序相悖。换个说法就是一组逆序对需要有两个下标 $i$ 与 $j$，满足 $i<j$ 且 $A_i>A_j$。

输入格式

• 第一行：两个整数 $N$ 与 $M$
• 接下来 $N$ 行：每行一个整数分别表示 $A_1,A_2,\dots,A_N$

输出格式

3 3
2 
1 
0

3
1
1

数据范围

• $30\%$ 的数据，$1\leq N,M\leq 100$
• $60\%$ 的数据，$1\leq N,M\leq 2000$
• $100\%$ 的数据，$1\leq N,M\leq 300,000$
• $0\leq A_i< M$

来源

改编自 ABC396F