I - Rotated Inversions Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

整数 N,M と長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

k=0,1,\ldots,M-1 に対して以下の問題を解いてください。

整数列 B=(B_1,B_2,\ldots,B_N) を B_i が A_i+k を M で割ったあまりとなるように定義したときの、 B の転倒数を求めてください。

転倒数とは 数列 (A_1,A_2,\dots,A_N) の転倒数とは、 1 \le i < j \le N かつ A_i > A_j を満たす整数組 (i,j) の個数を指します。

制約

  • 1\le N,M\le 2\times 10^5
  • 0\le A_i< M
  • 入力される値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \ldots A_N

出力

M 行出力せよ。

i 行目 (1\le i\le M) には、 k=i-1 の場合の答えを出力せよ。

入力例 1

3 3
2 1 0

出力例 1

3
1
1
  • k=0 のとき： B=(2 , 1 ,0) となります。このときの転倒数は 3 です。
  • k=1 のとき： B=(0,2,1) となります。このときの転倒数は 1 です。
  • k=2 のとき： B=(1,0,2) となります。このときの転倒数は 1 です。

入力例 2

5 6
5 3 5 0 1

出力例 2

7
3
3
1
1
5

入力例 3

7 7
0 1 2 3 4 5 6

出力例 3

0
6
10
12
12
10
6

Score : 500 points

Problem Statement

You are given integers N, M and a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N).

For k = 0, 1, \ldots, M-1, solve the following problem:

Define an integer sequence B = (B_1, B_2, \ldots, B_N) so that B_i is the remainder of A_i + k when divided by M. Find the inversion number in B.

What is the inversion number? The inversion number of a sequence (A_1, A_2, \dots, A_N) is the number of integer pairs (i, j) satisfying 1 \le i < j \le N and A_i > A_j.

Constraints

  • 1 \le N,M \le 2\times 10^5
  • 0 \le A_i < M
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N

Output

Print M lines.

The i-th line (1 \le i \le M) should contain the answer for the case k = i-1.

Sample Input 1

3 3
2 1 0

Sample Output 1

3
1
1
  • For k=0: B=(2, 1, 0). The inversion number is 3.
  • For k=1: B=(0, 2, 1). The inversion number is 1.
  • For k=2: B=(1, 0, 2). The inversion number is 1.

Sample Input 2

5 6
5 3 5 0 1

Sample Output 2

7
3
3
1
1
5

Sample Input 3

7 7
0 1 2 3 4 5 6

Sample Output 3

0
6
10
12
12
10
6