题目描述

问题 F 和问题 F2 是相同的问题，但约束条件和运行时间限制不同。

高桥君的仓库里有 $N$ 瓶葡萄酒，按左右方向排成一行。从左起第 $i$ 瓶葡萄酒的美味度为 $A_i$。
青木君现在要从这 $N$ 瓶葡萄酒中，恰好选出 $K$ 瓶来偷走。但是，高桥君非常警觉，如果满足以下条件，他就会发现葡萄酒被偷了：

• 存在某一段连续的 $D$ 瓶葡萄酒，其中被偷走的有 $2$ 瓶或以上（本题中 $D=2$）。

请计算在不被高桥君发现的所有偷盗方式中，偷走的葡萄酒美味度之和的总和。
由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入给出：

$N$ $K$ $D$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

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

输入输出样例 #1

输入 #1

4 2 2
1 4 2 3

输出 #1

14

输入输出样例 #2

输入 #2

5 3 2
4 7 5 3 8

输出 #2

17

输入输出样例 #3

输入 #3

12 4 2
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094

输出 #3

136993014

说明/提示

约束条件

• $D=2$
• $2 \leq N \leq 3 \times 10^5$
• $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,3,5$ 瓶葡萄酒。

由 ChatGPT 4.1 翻译