Cannot parse: expected a document, but the input is empty

合唱队形 (chorus)

• 输入：chorus.in
• 输出：chorus.out
• 时间限制：1 s
• 内存限制：128 MB

题目描述

学校合唱团有 $n$ 名同学，第 $i$ 名同学的身高为 $h_i$。任意两名同学的身高都不同。

排练时，老师会先让这 $n$ 名同学按某个顺序依次走上舞台，然后按照下面的规则把他们插入到当前队形中：

• 第一名同学直接站入空队形。
• 从第二名同学开始，若当前同学比上一名走上舞台的同学高，则站到当前队形的最右端。
• 若当前同学比上一名走上舞台的同学矮，则站到当前队形的最左端。

现在给定老师希望得到的最终队形，即从左到右的身高序列 $h_1,h_2,\dots,h_n$。

请你计算有多少种不同的上台顺序，可以得到这个最终队形。由于答案可能很大，请对 $998244353$ 取模。

输入格式

从文件 chorus.in 中读入数据。

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $h_1,h_2,\dots,h_n$，表示最终队形中从左到右每名同学的身高。

输出格式

输出到文件 chorus.out 中。

输出一个整数，表示能够得到该最终队形的上台顺序数量，对 $998244353$ 取模。

样例1输入

4
3 1 2 4

样例1输出

2

样例1解释

有 $2$ 种上台顺序可以得到最终队形 $[3,1,2,4]$：

• $[1,2,4,3]$。
• $[2,1,4,3]$。

可以验证，不存在其他上台顺序能够得到相同的最终队形。

数据范围

对于所有数据，$1 \le n \le 1000$，$1000 \le h_i \le 2000$，保证所有 $h_i$ 两两不同。每个测试点 $5$ 分。