题目描述

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

3
1 3 2

4

8
3 7 1 7 4 2 5 1

126

提示

样例解释

对于样例 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$。