背景

试题来自 清华大学学生算法协会。

题目描述

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$ 取模。

4
1 4 2 3

10

7
5 1 4 2 6 3 7

340

提示

在第一个样例中，他们能够获得的所有可能排列如下：

$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$

翻译由 DeepSeek V4 Pro 完成