配点: 100 点
問題
N 糖果,i 糖果的美味是 A_i 。
f(l,r) (1 \leq l \leq r \leq N) , 从第l 起 对于第 r 号糖果,其定义为在以下条件下所吃的糖果的美味度总和的最大值。 不要连续吃
条件:2 块。也就是说, 一切满足l \leq i < r 一切满足的 i 中,i 与第三颗糖果 你不能同时吃掉 i+1 糖果。
当品尝每种糖果的味道时, 所有满足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).
小課題
- (10 点) N \leq 300.
- (20 点) A_i \leq 300 (1 \leq i \leq N).
- (70 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N A_1 \cdots A_N
出力
在标准输出上, 在1 \leq l \leq r \leq N 的元组 关于 (l,r) 关于 f(l,r) 的总和 编写一个程序求除以 998\,244\,353 后的余数 输出为 1 行。 在
入力例 1
3 1 2 3
出力例 1
15
l=2,r=3 的情况下,2 th 和 3 我两个糖果都吃不下去, 由于最好只吃3 糖果, 它变成f(l,r)=3 。 由于吃第 l=1,r=3 的情况下,1 th 和 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 。 由于吃第
入力例 2
4 1 100 100 1
出力例 2
805
入力例 3
1 1000000000
出力例 3
1755647
998\,244\,353 后的余数。
入力例 4
10 850534838 749655434 745817507 991867417 645519349 373697182 427765279 182404140 260664174 366393413
出力例 4
554337161