Prediction
Contest: Educational Codeforces Round 145 (Rated for Div. 2)
Difficulty rating: 2800
Tags: combinatorics, dp, math

Consider a tournament with $$$n$$$ participants. The rating of the $$$i$$$-th participant is $$$a_i$$$.

The tournament will be organized as follows. First of all, organizers will assign each participant an index from $$$1$$$ to $$$n$$$. All indices will be unique. Let $$$p_i$$$ be the participant who gets the index $$$i$$$.

Then, $$$n-1$$$ games will be held. In the first game, participants $$$p_1$$$ and $$$p_2$$$ will play. In the second game, the winner of the first game will play against $$$p_3$$$. In the third game, the winner of the second game will play against $$$p_4$$$, and so on — in the last game, the winner of the $$$(n-2)$$$-th game will play against $$$p_n$$$.

Monocarp wants to predict the results of all $$$n-1$$$ games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings $$$x$$$ and $$$y$$$ play, and $$$|x - y| > k$$$, the participant with the higher rating wins. But if $$$|x - y| \le k$$$, any of the two participants may win.

Among all $$$n!$$$ ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all $$$n-1$$$ games. Since the answer can be large, print it modulo $$$998244353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$0 \le k \le 10^9$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$).

Output format:
Print one integer — the number of ways to assign the indices to the participants so that Monocarp can predict the results of all $$$n-1$$$ games.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first example, a match with any pair of players can be predicted by Monocarp, so all $$$24$$$ ways to assign indices should be counted.

In the second example, suitable ways are $$$[1, 3, 2]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2$$$] and $$$[3, 2, 1]$$$.

Example input:
4 3
7 12 17 21

Example output:
24

Example input:
3 7
4 9 28

Example output:
4

Editorial:
We need some sort of better criterion other than "all matches can be predicted" first. Suppose the ratings of the participants are $$$r_1, r_2, \dots, r_n$$$ in the order of their indices. Then, if all games are predictable, the $$$i$$$-th game should be won by the participant with the rating equal to $$$\max \limits_{j=1}^{i+1} r_j$$$; and in the $$$(i+1)$$$-th game, they will play against the participant with rating $$$r_{i+2}$$$. So, in order for each game to be predictable, the maximum on each prefix should be different from the next element by at least $$$k+1$$$. This is the criterion we will use.
So, we will try to count the number of orderings meeting this condition. One very important observation we need to make is that, if we remove several participants with the lowest ratings from the ordering, that ordering still satisfies the condition (for each element, either the prefix before it is removed completely, or the maximum on it is unchanged). So, this allows us to construct the correct ordering by placing the sportsmen from the maximum rating to the minimum rating, and making sure that on every step, the order stays correct.
Okay. Let's reverse the ratings array, and try to write the following dynamic programming: $$$dp_i$$$ is the number of correct orderings of the first $$$i$$$ sportsmen (the $$$i$$$ highest-rated sportsmen, since we reversed the ratings array). Let's try to place the next sportsman. We run into the following issue: for some orderings of the first $$$i$$$ sportsmen, it is possible to place the next one anywhere (these orderings are where the first sportsman in the ordering doesn't conflict with the sportsman we are trying to place); but for other orderings, some positions might be forbidden. And to keep track of which positions are forbidden, and for which sportsmen, we probably need some additional states for the dynamic programming, which we don't really want to since $$$O(n)$$$ states is probably the most we can allow.
Okay, so let's avoid this issue entirely. We don't like the orderings where the next sportsman can't be placed anywhere, so let's find a way to "ignore" them:
• discard the previous definition of $$$dp_i$$$. Now, let $$$dp_i$$$ is the number of correct orderings of the $$$i$$$ highest-rated sportsmen where the first element in the ordering doesn't conflict with any of the elements we haven't placed yet;
• when we place the next sportsman, in case it becomes the first element and conflicts with some of the elements we haven't placed yet, we place those conflicting elements as well.
So, this leads to the following transitions in the dynamic programming:
• if we place the $$$(i+1)$$$-th sportsman on any position other than the first one, there are $$$i$$$ ways to do it, and we transition from $$$dp_{i}$$$ to $$$dp_{i+1}$$$;
• otherwise, if we place the $$$(i+1)$$$-th sportsman on the first position, let $$$f(i+1)$$$ be the last sportsman "conflicting" with the sportsman $$$i+1$$$. Let's try placing all sportsmen from $$$i+2$$$ to $$$f(i+1)$$$ before placing the sportsman $$$i+1$$$. They cannot be placed on the first position (otherwise they will conflict either with each other or with the sportsman $$$i+1$$$), so the first one can be placed in $$$i$$$ ways, the second one — in $$$(i+1)$$$ ways, and so on; this product can be easily calculated in $$$O(1)$$$ by preparing factorials and inverse factorials. So, then we transition from $$$dp_i$$$ to $$$dp_{f(i+1)}$$$.
There is a special case in our dynamic programming. It should start with $$$dp_1 = 1$$$, but what if the $$$1$$$-st sportsman conflicts with someone? Then the ordering of the first $$$i=1$$$ sportsmen is incorrect. In this case, the answer is $$$0$$$ since the $$$1$$$-st and the $$$2$$$-nd sportsmen are conflicting.
Overall complexity of this solution is $$$O(n \log MOD)$$$ or $$$O(n + \log MOD)$$$ depending on your implementation.