AT_arc186_d [ARC186D] Polish Mania

[problemUrl]: https://atcoder.jp/contests/arc186/tasks/arc186_d 空でない非負整数列 $ (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) $ が与えられます。辞書順で $ (A_1,\ A_2,\ \dots,\ A_N) $ 以下である、長さ $ N $ の Polish 数列の数を $ 998244353 $ で割ったあまりを求めてください。 数列の辞書順とは？数列 $ S\ =\ (S_1,S_2,\ldots,S_{|S|}) $ が数列 $ T\ =\ (T_1,T_2,\ldots,T_{|T|}) $ より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、$ |S|,\ |T| $ はそれぞれ $ S,\ T $ の長さを表します。 1. $ |S|\ \lt\ |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 $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (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\ \lt\ N $ - 入力はすべて整数 ### Sample Explanation 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) $ は、 $ (2) $ と $ 2 $ つの Polilsh 数列 $ (0) $ と $ (0) $ をこの順に連結したものと一致するため、Polish である - $ (1,\ 2,\ 0,\ 0) $ は、 $ (1) $ と $ 1 $ つの Polilsh 数列 $ (2,\ 0,\ 0) $ をこの順に連結したものと一致するため、Polish である - $ (1,\ 1,\ 2,\ 0,\ 0) $ は、 $ (1) $ と $ 1 $ つの Polilsh 数列 $ (1,\ 2,\ 0,\ 0) $ をこの順に連結したものと一致するため、Polish である - $ (1,\ 1,\ 1,\ 2,\ 0,\ 0) $ は、 $ (1) $ と $ 1 $ つの Polilsh 数列 $ (1,\ 1,\ 2,\ 0,\ 0) $ をこの順に連結したものと一致するため、Polish である