P14639 【OIMO Round 1】世界线

X 正在编写她的小说，她需要为这本小说设定一条世界线，也就是各个事件发生的时间次序。 X 已经想好了 $n$ 个事件，第 $i$ 个事件有一个 $1$ 到 $n$ 内的类型 $a_i$。X 要将这 $n$ 个事件的**类型**排成一个序列 $B$。 X 希望小说的内容跌宕起伏，所以对于 $B$ 的每个前缀 $b_1,\dots,b_k$，$b_k$ 必须是该前缀的最大值或最小值。 X 想要知道，符合要求的**本质不同**的序列 $B$ 共有多少种？ 由于数量实在是太大了，X 让你将答案对 $998244353$ 取模。 **本质不同**：定义两个长度为 $n$ 的序列 $X$ 和 $Y$ 是本质不同的，当且仅当存在 $1\le i\le n$，使得 $x_i\neq y_i$。

第一行一个正整数 $n$，表示事件的个数。 第二行 $n$ 个正整数，第 $i$ 个正整数为 $a_i$。

一行一个正整数，表示答案对 $998244353$ 取模后的值。

#### 样例解释 对于样例 1，一共有以下四种序列是符合要求的： - $[1,2,3]$； - $[2,1,3]$； - $[2,3,1]$； - $[3,2,1]$。 **本题采用捆绑测试**。 - Subtask 1（20 points）：$n \le 10$。 - Subtask 2（80 points）：无特殊限制。 对于所有测试数据，$1 \le n \le 10^6$，$1 \le a_i \le n$。