P17132 [ICPC 2025 Shanghai R] Yet another permutation problem

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

Yana、Mino、White 和 Huzz 是最好的朋友。 终于完成了教练那些繁重的任务后，Huzz 理应休息一下。在一个慵懒的午后，世界仿佛慢了下来，一切都包裹在即将到来的黄昏那温暖而金黄的光晕中。微风轻拂，不过是搅动了透过大橡树叶斜斜洒下的阳光中飞舞的微尘。 在这昏沉而惬意的空虚中，Huzz 在他的软鲨鱼玩具里发现了一个排列。他决定把它分享给朋友们玩玩。 Mino 喜欢分割。他可以将这个排列分割成若干个连续段。 Yana 喜欢交换。他可以选择一个连续段，并交换其中的最大值和最小值。 具体来说，他们可以**以任意顺序、任意次数**执行以下两种操作： - **分割：** 选择一个长度大于 $1$ 的连续段。然后在其中选择一个位置，将其分割为两个相邻的连续段。例如，$(a_i, \ldots, a_j)$ 可以分割为 $(a_i, \ldots, a_k)$ 和 $(a_{k+1}, \ldots, a_j)$，其中 $i \le k < j$。 - **交换：** 选择一个连续段，交换其中的最大值和最小值。 执行任意次操作后，他们停下来，所有得到的段按原有顺序合并，形成一个新的排列。 White 喜欢计数。她想知道——他们能得到多少个不同的排列？ 由于结果可能非常大，你只需要求出答案对 $998\,244\,353$ 取模的值。

第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示排列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$)，表示该排列。保证 $\{a_n\}$ 是一个排列。

输出一个整数，表示他们能得到的不同排列的数量，对 $998\,244\,353$ 取模。

在第一个样例中，他们能够获得的所有可能排列如下： $(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$ 翻译由 DeepSeek V4 Pro 完成