問題

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)．

小課題

1. (10 点) N \leq 300．
2. (20 点) A_i \leq 300 (1 \leq i \leq N)．
3. (70 点) 追加の制約はない．

入力例 1

3
1 2 3

出力例 1

15

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 になる．

入力例 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