序列取反问题

题号：NC202431
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 $n$ 个牛牛排成一排，从头到尾编号为 $0$ 到 $n-1$ ，牛牛们都有一个可爱值，对于牛牛 $i$ ，记它的可爱值为 $a_i$ ， $a_i>i$ ，特别地，我们令 $a_0=n$ 。这次我们的任务是把牛牛全部变成快乐的牛牛，起初所有牛牛都不快乐，每次我们从不快乐的牛牛中等概率选择一个，设选出来的是 $x$ ，把编号 $x$ 到 $a_x-1$ 中的不快乐的牛牛全部变成快乐的牛牛，一次这样的操作记为1步。问让全部不快乐的牛牛都变成快乐的牛牛的期望步数。
由于牛牛们都很有特色，所以对于任意 $i,j$ ，均满足条件：若 $i<j$ ，则 $a_i-1<j$ ， $a_i \geq a_j$ 这两个条件一定满足其中1个。
答案对998244353取模。
设答案为 $\frac{p}{q}$ ，其中 $gcd(p,q)=1$ ，输出 $ans$ ，要求 $ans$ 为满足 $(ans*q)\%MOD=p$ 的最小整数。
输入时，给出数 $n$ ， $a_i$ 将以数组 $a$ 的形式给出，详细见样例。

示例1

输入

复制

5,[5,4,3,4,5]

返回值

复制

665496238

说明

答案为8/3，在对998244353取模的情况下是665496238

示例2

输入

复制

6,[6,4,3,4,6,6]

返回值

复制

备注:

n<=200000，i<=ai<=n