F - Almost Sorted 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : {500} 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) および正整数 D が与えられます。

A を並び替えることで得られる整数列 B=(B_1, B_2, \ldots, B_N) であって、次の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

  • すべての i\ (1\leq i\leq N-1) に対して B_{i+1}\geq B_i-D が成り立つ。

制約

  • 2\leq N\leq 2\times 10^5
  • 1\leq D\leq 10^6
  • 1\leq A_i\leq 10^6
  • 入力は全て整数

入力

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

N D
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

4 1
5 2 1 2

出力例 1

3

条件を満たす整数列は (1,2,2,5),(2,1,2,5),(2,2,1,5) の 3 つです。

入力例 2

5 10
20 40 60 80 100

出力例 2

1

入力例 3

15 12345
18270 31252 27543 31406 22271 13402 12279 25697 18349 27615 39360 22790 32581 23990 36154

出力例 3

858152905

Score : 500 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and a positive integer D.

Find the number, modulo 998244353, of integer sequences B=(B_1, B_2, \ldots, B_N) that can be obtained by rearranging A and satisfy the following condition:

  • B_{i+1}\geq B_i-D holds for all i\ (1\leq i\leq N-1).

Constraints

  • 2\leq N\leq 2\times 10^5
  • 1\leq D\leq 10^6
  • 1\leq A_i\leq 10^6
  • All input values are integers.

Input

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

N D
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

4 1
5 2 1 2

Sample Output 1

3

The integer sequences satisfying the condition are (1,2,2,5),(2,1,2,5),(2,2,1,5), which are three sequences.

Sample Input 2

5 10
20 40 60 80 100

Sample Output 2

1

Sample Input 3

15 12345
18270 31252 27543 31406 22271 13402 12279 25697 18349 27615 39360 22790 32581 23990 36154

Sample Output 3

858152905