#P12374. 「LAOI-12」Sigma

「LAOI-12」Sigma

题目背景

题目描述

给定一个长度为 nn 的序列 aa,求对于所有区间 [l,r][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[1,rl+1]k\in[1,r-l+1] 满足 k>al+k1k>a_{l+k-1} 则认为该表达式值为 00,结果对 998244353998244353 取模。

输入格式

第一行共一个正整数 nn,表示序列长度。
第二行共 nn 个正整数,表示序列 aa

输出格式

共一行,一个正整数表示答案,结果对 998244353998244353 取模。

3
1 3 2
29
5
8 9 12 7 1
81303

提示

样例解释

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

  1. 对于 [1,1][1,1],答案即为 i1=11i1=1\sum\limits_{i_1=1}^1i_1=1
  2. 对于 [2,2][2,2],答案即为 i1=13i1=6\sum\limits_{i_1=1}^3i_1=6
  3. 对于 [3,3][3,3],答案即为 i1=12i1=3\sum\limits_{i_1=1}^2i_1=3
  4. 对于 [1,2][1,2],答案即为 $\sum\limits_{i_1=1}^1\sum\limits_{i_2=2}^3i_1+i_2=7$;
  5. 查询 [2,3][2,3],答案即为 $\sum\limits_{i_1=1}^3\sum\limits_{i_2=2}^2 i_1+i_2=12$;
  6. 查询 [1,3][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>23>2

数据范围

本题采用捆绑测试。

子任务编号 nn 特殊性质 分值
11 6\le 6 ai8a_i\le 8 55
22 102\le 10^2 3030
33 5×103\le 5\times10^3 所有 aia_i 相等 1010
44 5×103\le 5\times 10^3 5555

对于 100%100\% 的测试数据,满足 1n5×1031\le n\le 5\times 10^31ai1091\le a_i\le 10^9