#P18565. Dividing Chains

Dividing Chains

Dividing Chains

对于一个序列 z1,z2,…,znz_1,z_2,\ldots,z_n,考虑集合 S={1,n+1}S=\{1,n+1\}。小青鱼可以执行以下操作恰好 n−1n-1 次:

  1. 选择一个整数 xx,满足 x∉Sx\notin S 且 1<x≤n1<x\le n。
  2. 令 ll 为 xx 在 SS 中的前驱,即 SS 中小于 xx 的最大整数。
  3. 令 rr 为 xx 在 SS 中的后继,即 SS 中大于 xx 的最小整数。
  4. 选择不做任何改变,或者对序列 zz 执行以下更新:将子段 zl,zl+1,…,zr−1z_l,z_{l+1},\ldots,z_{r-1} 整体反转,即对所有 l≤i≤r−1l\le i\le r-1,同时令原 ziz_i 移到位置 r−1−(i−l)r-1-(i-l)。
  5. 更新 S←S∪{x}S\leftarrow S\cup\{x\}。

显然,最后 SS 会变为 {1,2,…,n,n+1}\{1,2,\ldots,n,n+1\}。

给定一个单调不降的序列 a1,a2,…,ana_1,a_2,\ldots,a_n,请计算有多少个不同的序列 z1,z2,…,znz_1,z_2,\ldots,z_n 满足:存在一种执行上述操作的方法,能够将 zz 变成 aa。输出这个数量对 998244353998244353 取模的结果。

这个问题让小青鱼感到莫名其妙,于是他请你来解决。

输入格式

输入仅包含一组数据。

第一行包含一个整数 nn(1≤n≤5001\le n\le500)。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,保证

1≤a1≤a2≤⋯≤an≤n.1\le a_1\le a_2\le\cdots\le a_n\le n.

输出格式

输出一行一个整数,表示满足条件的不同序列的数量对 998244353998244353 取模的结果。

原样例 1

3
2 3 3
3

原样例 2

5
1 1 3 3 5
29

原样例 3

9
1 2 3 5 5 6 7 8 9
26276