AT_otemae2019_h.美味しい飴 (Candy is Delicious)

有 $N$ 个糖果，第 $i$ 个糖果的美味度为 $A_i$。

定义 $f(l,r)$（$1 \leq l \leq r \leq N$）为从第 $l$ 个到第 $r$ 个糖果中，在如下条件下能吃到的糖果美味度总和的最大值。

条件：不能连续吃两个糖果。也就是说，对于所有满足 $l \leq i < r$ 的 $i$，不能同时吃第 $i$ 个和第 $i+1$ 个糖果。

给定每个糖果的美味度，请编写程序，计算所有满足 $1 \leq l \leq r \leq N$ 的 $(l, r)$ 组合的 $f(l, r)$ 之和，并输出其对 $998\,244\,353$ 取模的结果。

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

请输出所有满足 $1 \leq l \leq r \leq N$ 的 $(l, r)$ 组合的 $f(l, r)$ 之和对 $998\,244\,353$ 取模的结果，输出一行。

限制条件

• $1 \leq N \leq 200\,000$。
• $1 \leq A_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。

子任务

1. （10 分）$N \leq 300$。
2. （20 分）$A_i \leq 300$（$1 \leq i \leq N$）。
3. （70 分）无额外限制。

样例解释 1

当 $l=2, r=3$ 时，不能同时吃第 2 个和第 3 个糖果，最优是只吃第 3 个糖果，所以 $f(l,r)=3$。当 $l=1, r=3$ 时，最优是吃第 1 个和第 3 个糖果，所以 $f(l,r)=1+3=4$。输出的值为 $f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+4+2+3+3=15$。

样例解释 3

请输出对 $998\,244\,353$ 取模的结果。

由 ChatGPT 4.1 翻译