AT_otemae2019_h 美味しい飴 (Candy is Delicious)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_h $ N $ 個の飴があり，$ i $ 番目の飴の美味しさは $ A_i $ である． $ f(l,r) $ $ (1\ \leq\ l\ \leq\ r\ \leq\ N) $ を，$ l $ 番目から $ r $ 番目の飴において下記の条件の下で，食べた飴の美味しさの総和の最大値と定義する． 条件：$ 2 $ 個連続して食べない．すなわち，$ l\ \leq\ i\

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ \cdots $ $ A_N $

標準出力に，$ 1\ \leq\ l\ \leq\ r\ \leq\ N $ を満たすすべての組 $ (l,r) $ についての $ f(l,r) $ の総和を $ 998\,244\,353 $ で割った余りを $ 1 $ 行で出力せよ．

### 制約 - $ 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 $ 点) 追加の制約はない． ### Sample Explanation 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 $ になる． ### Sample Explanation 3 $ 998\,244\,353 $ で割った余りを出力せよ．