AT_arc120_f2 [ARC120F2] Wine Thief

**问题 F 和问题 F2 是相同的问题，但约束条件和运行时间限制不同。** 高桥君的仓库里有 $N$ 瓶葡萄酒，按左右方向排成一列。从左边数第 $i$ 瓶葡萄酒的美味度为 $A_i$。 青木君现在要从这 $N$ 瓶葡萄酒中，恰好选出 $K$ 瓶进行偷窃。但是，高桥君非常警觉，如果满足以下条件，他就会发现被偷了： - 存在连续排列的 $D$ 瓶葡萄酒，其中被偷走的有 $2$ 瓶或以上。 请你求出所有不会被高桥君发现的偷窃方案中，偷走的葡萄酒美味度之和的总和。 由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入以如下格式从标准输入给出： > $N$ $K$ $D$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出答案对 $998244353$ 取模的结果。

## 约束条件 - $2 \leq D \leq N \leq 10^6$ - $1 \leq K \leq \left\lceil \frac{N}{D} \right\rceil$（$\left\lceil x \right\rceil$ 表示不小于 $x$ 的最小整数） - $1 \leq A_i < 998244353$ - 输入中的所有值均为整数 ## 样例解释 1 偷窃方案及其美味度之和如下： - 偷第 $1$ 瓶和第 $3$ 瓶：美味度之和为 $1 + 2 = 3$ - 偷第 $1$ 瓶和第 $4$ 瓶：美味度之和为 $1 + 3 = 4$ - 偷第 $2$ 瓶和第 $4$ 瓶：美味度之和为 $4 + 3 = 7$ 因此答案为 $3 + 4 + 7 = 14$。 ## 样例解释 2 偷窃方案及其美味度之和如下： - 偷第 $1$ 瓶和第 $4$ 瓶：美味度之和为 $1 + 7 = 8$ - 偷第 $1$ 瓶和第 $5$ 瓶：美味度之和为 $1 + 3 = 4$ - 偷第 $2$ 瓶和第 $5$ 瓶：美味度之和为 $5 + 3 = 8$ 由 ChatGPT 4.1 翻译