UOJ Logo Universal Online Judge

UOJ

附件下载 统计

看起来 UOJ 正在举办十周年庆典!只要通过完成挑战,收集到宝贵的比特,就可以兑换奖品!

其中一项挑战是吃十周年大蛋糕!蛋糕有 $n$ 层,第 $i$ 层大小是 $c_i$,为了防止蛋糕倒塌,保证 $c$ 单调不增。

作为挑战者,主办方初始会将第 $1$ 层蛋糕给你,在挑战的过程中,将会把剩下的蛋糕按照标号从小到大的顺序根据规则依次给你。你会重复如下操作,直到手上没有蛋糕:

  • 吃掉你已有的最大的一层蛋糕,假设吃掉的这层蛋糕的大小为 $x$。
  • 如果主办方有至少 $x$ 层蛋糕,主办方会按照顺序,将接下来的 $x$ 层蛋糕 转交 给你。
  • 否则如果主办方的蛋糕不足 $x$ 层,只有 $y$ 层,那么主办方会将剩余的蛋糕全部 转交 给你,并补偿你 $x-y$ 个比特。

似乎如果这样,那么所有的挑战者都可以吃到所有的蛋糕,并获得一样的比特!真是其乐融融!但是谁都没有注意到,一只爱吃蛋糕的小老鼠,也偷偷溜进了庆典!

偷吃蛋糕

由于这只小老鼠过于喜欢吃蛋糕,每当主办方想要将至少一层蛋糕 转交 给你的时候,这只小老鼠都会突然出现并随机抢走其中的一块即将 转交 给你的蛋糕!

为了挑战最终谜题,现在你作为挑战者想知道,你在这次游戏中期望能获得多少个比特呢?答案对 $998244353$ 取模。

输入格式

第一行输入一个正整数 $n$。

第二行输入 $n$ 个单调不增的正整数 $c_1, c_2, \dots, c_n$。

输出格式

一行一个整数,表示答案对 $998244353$ 取模后的余数。

样例一

input

3
1 1 1

output

0

explanation

在你吃完第一层蛋糕后,当主办方将第二层蛋糕转交给你的过程中,小老鼠偷走了第二层蛋糕,因此你无法吃完所有蛋糕,也无法获得比特。

样例二

input

5
3 3 2 1 1

output

3

explanation

在你吃完第一层蛋糕后,主办方将第 $2$ 到 $4$ 层蛋糕转交给你的过程中,小老鼠会随机偷走这三层中的一层。下一次转交蛋糕必然是只转交最后一层,因此最后一层蛋糕也必然会被小老鼠偷走,偷取第 $2, 3, 4$ 层蛋糕则分别可以获得 $2, 3, 4$ 个比特,因此期望可以获得 $3$ 个比特。

样例三

input

18
5 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1

output

199648871

样例四~八

见附件下载。

限制与约定

对于所有数据,保证 $1 \leq n \leq 2000$,$1 \leq c_i \leq n$,且 $c$ 单调不增。

子任务编号 $n \leq $ $c_1 \leq $ 分值
$1$ $18$ $18$ $10$
$2$ $50$ $50$ $15$
$3$ $200$ $20$ $10$
$4$ $500$ $500$ $15$
$5$ $1000$ $22$ $20$
$6$ $2000$ $2000$ $30$

时间限制:$0.6\texttt{s}$

空间限制:$512\texttt{MB}$