擂台 - 代码源竞赛平台

题目描述

社区举办一场擂台赛，$n$ 名选手依次排成一行，初始时从左到右编号为 $1,2,\ldots,n$。第 $i$ 名选手的实力为 $a_i$，所有选手的实力两两不同。

每场比赛从当前队伍中选出相邻的两名选手。实力较强的一方获胜，另一方退出队伍。剩余选手的相对顺序保持不变，编号也始终沿用初始编号。比赛不断进行，直到队伍中只剩一名选手。

工作人员用一个长度为 $n$ 的数组 $b$ 记录比赛结果：如果选手 $i$ 被选手 $j$ 淘汰，就令 $b_i=j$；如果选手 $i$ 留到了最后，就令 $b_i=0$。

请计算可能得到多少种不同的记录。只要两个数组在某个位置上的数不同，就认为它们是不同的记录；不同的比赛安排若得到同一个数组，只计为一种。答案对 $998244353$ 取模。

输入格式

第一行包含一个正整数 $n$，为参加擂台赛的选手数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 为选手 $i$ 的实力。

输出格式

输出一个非负整数，表示不同记录的数量对 $998244353$ 取模的结果。

样例

4
4 1 3 2

4

3
1 3 2

1

样例解释

样例 1：四种可能的记录分别为 $(0,1,1,1)$、$(0,3,1,1)$、$(0,1,1,3)$ 和 $(0,3,1,3)$。例如，依次让选手 $2$ 与 $3$、选手 $3$ 与 $4$、选手 $1$ 与 $3$ 比赛，可以得到最后一种记录。

样例 2：选手 $2$ 必须分别淘汰选手 $1$ 和 $3$。这两场比赛的先后次序可以不同，最终记录都是 $(2,0,2)$。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$20$	$8$	无
$2$	$20$	$60$
$3$	$20$	$500$	A
$4$	$40$		无

特殊性质 A：数组 $a$ 严格递增或严格递减。

对于 $100\%$ 的数据，$1\le n\le500$，$1\le a_i\le10^9$，且所有 $a_i$ 两两不同。