时空限制

1S/512M

题目描述

给定一个长度为 $m$ 的序列 $b$，我们称 $b$ 是“好序列”，当且仅当序列的极差不超过一个常数 $k$，即：

其中，符号 $\max_{i=1}^m b_i$ 表示序列 $b$ 中 $m$ 个元素的最大值，$\min_{i=1}^m b_i$ 表示序列 $b$ 中 $m$ 个元素的最小值。

现在给定一个长度为 $n$ 的序列 $a$，你需要求出 $a$ 有多少个非空子序列是“好序列”。

由于答案可能很大，请你对 $998244353$ 取模后输出。

注：一个序列 $x$ 是另一个序列 $y$ 的子序列，当且仅当 $x$ 可以通过 $y$ 删除零个或若干个元素（保持剩余元素相对顺序不变）得到。

格式

输入格式

第一行包含两个整数 $n, k$，分别表示序列的长度和题目描述中的常数 $k$。

第二行包含 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式

输出一行一个整数，表示“好序列”子序列的数量模 $998244353$ 的结果。

样例

样例输入 #1

4 3
4 2 6 8

样例输出 #1

7

样例解释 #1

原序列为 $\{4, 2, 6, 8\}$，满足条件的子序列如下：

• 长度为 $1$：$\{4\}, \{2\}, \{6\}, \{8\}$（极差均为 $0$），共 $4$ 个。
• 长度为 $2$：
  • $\{4, 2\}$：极差 $|4-2|=2 \le 3$，合法。
  • $\{4, 6\}$：极差 $|4-6|=2 \le 3$，合法。
  • $\{6, 8\}$：极差 $|6-8|=2 \le 3$，合法。
  • 其他如 $\{2, 8\}$ 极差为 $6$，$\{2, 6\}$ 极差为 $4$ 等均不合法。
• 长度 $\ge 3$：无合法子序列。 总计 $4 + 3 = 7$ 个。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le k, a_i \le 10^9$。