题目背景

题目描述

给定一个长度为 $n$ 的序列 $a$，求对于所有区间 $[l,r]$ 的 $\sum\limits_{i_1=1}^{a_l}\sum\limits_{i_2=2}^{a_{l+1}}\sum\limits_{i_3=3}^{a_{l+2}}\dots\sum\limits_{i_{r-l+1}=r-l+1}^{a_{r}}i_1+i_2+i_3+\dots+i_{r-l+1}$ 值的和，若存在 $k\in[1,r-l+1]$ 满足 $k>a_{l+k-1}$ 则认为该表达式值为 $0$，结果对 $998244353$ 取模。

输入格式

第一行共一个正整数 $n$，表示序列长度。
第二行共 $n$ 个正整数，表示序列 $a$。

输出格式

共一行，一个正整数表示答案，结果对 $998244353$ 取模。

3
1 3 2

29

5
8 9 12 7 1

81303

提示

样例解释

对于样例一中的区间贡献分别如下：

1. 对于 $[1,1]$，答案即为 $\sum\limits_{i_1=1}^1i_1=1$；
2. 对于 $[2,2]$，答案即为 $\sum\limits_{i_1=1}^3i_1=6$；
3. 对于 $[3,3]$，答案即为 $\sum\limits_{i_1=1}^2i_1=3$；
4. 对于 $[1,2]$，答案即为 $\sum\limits_{i_1=1}^1\sum\limits_{i_2=2}^3i_1+i_2=7$；
5. 查询 $[2,3]$，答案即为 $\sum\limits_{i_1=1}^3\sum\limits_{i_2=2}^2 i_1+i_2=12$；
6. 查询 $[1,3]$，答案即为 $\sum\limits_{i_1=1}^1\sum\limits_{i_2=2}^3\sum\limits_{i_3=3}^2 i_1+i_2+i_3=0$，因为 $3>2$。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的测试数据，满足 $1\le n\le 5\times 10^3$，$1\le a_i\le 10^9$。