AT_arc186_d.[ARC186D] Polish Mania

非空非负整数序列 $(V_1,\ V_2,\ \dots,\ V_M)$ 被称为 Polish，其递归定义如下：

• 存在 $V_1$ 个 Polish 序列 $W_1,\ W_2,\ \dots,\ W_{V_1}$，使得将序列 $(V_1),\ W_1,\ W_2,\ \dots,\ W_{V_1}$ 按顺序连接后，恰好得到序列 $(V_1,\ V_2,\ \dots,\ V_M)$。

特别地，序列 $(0)$ 是 Polish。

给定一个长度为 $N$ 的非负整数序列 $(A_1,\ A_2,\ \dots,\ A_N)$。请你求出，长度为 $N$、字典序不大于 $(A_1,\ A_2,\ \dots,\ A_N)$ 的 Polish 序列的个数，对 $998244353$ 取模。

关于序列的字典序：设 $S = (S_1,S_2,\ldots,S_{|S|})$，$T = (T_1,T_2,\ldots,T_{|T|})$，则 $S$ 的字典序小于 $T$，当且仅当满足以下两条之一（其中 $|S|,\ |T|$ 分别为 $S,T$ 的长度）：

1. $|S| < |T|$ 且 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$。
2. 存在整数 $1 \leq i \leq \min\lbrace |S|,\ |T| \rbrace$，使得以下两点同时成立：
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$；
   • $S_i$ 小于 $T_i$（按数值比较）。

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

请输出满足条件的序列个数，对 $998244353$ 取模。

数据范围

• $1\leq N \leq 3\times 10^5$
• $0\leq A_i < N$
• 输入均为整数

样例解释 1

$(1,\ 1,\ 1,\ 1,\ 1,\ 0)$ 和 $(1,\ 1,\ 1,\ 2,\ 0,\ 0)$ 满足条件。$(1,\ 1,\ 1,\ 2,\ 0,\ 0)$ 是 Polish，可以如下验证：

• 如题目所述，$(0)$ 是 Polish；
• $(2,\ 0,\ 0)$ 是 Polish，因为它等于 $(2)$ 与两个 Polish 序列 $(0)$ 和 $(0)$ 按顺序连接；
• $(1,\ 2,\ 0,\ 0)$ 是 Polish，因为它等于 $(1)$ 与一个 Polish 序列 $(2,\ 0,\ 0)$ 按顺序连接；
• $(1,\ 1,\ 2,\ 0,\ 0)$ 是 Polish，因为它等于 $(1)$ 与一个 Polish 序列 $(1,\ 2,\ 0,\ 0)$ 按顺序连接；
• $(1,\ 1,\ 1,\ 2,\ 0,\ 0)$ 是 Polish，因为它等于 $(1)$ 与一个 Polish 序列 $(1,\ 1,\ 2,\ 0,\ 0)$ 按顺序连接。

由 ChatGPT 4.1 翻译