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 翻译