[R75F]旋律编排 - 代码源竞赛平台

时空限制

2S/256M

题目描述

编曲台会依次收到 $n$ 个音符，每个音符的音高等级各不相同，恰好为 $1,2,\ldots,n$。这些音符按照排列 $p_1,p_2,\ldots,p_n$ 的顺序到达。

开始时旋律轨道为空。处理音符 $p_i$ 时，可以把它接在当前旋律的最左端，也可以接在最右端。处理第一个音符时，两种放法都会得到相同的单音符旋律。

设最终从左到右的音高等级为 $b_1,b_2,\ldots,b_n$。为了使音高走势不断转折，对于每个内部位置 $2\le i<n$，都应满足

$$b_{i-1}<b_i>b_{i+1}$$

或

$$b_{i-1}>b_i<b_{i+1}.$$

当 $n\le 2$ 时，任何能够得到的最终排列都视为符合要求。

请你求出能够得到多少个不同的、符合要求的最终排列，并将答案对 $998244353$ 取模。

这里统计的是不同的最终排列，而不是放置音符的过程。如果两种放置过程得到完全相同的最终排列，它们只计一次。两个最终排列只要至少有一个位置上的音高等级不同，就视为不同。

格式

输入格式

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

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$。

输出格式

输出一个整数，表示不同合法最终排列的数量对 $998244353$ 取模后的结果。

样例

样例输入 #1

3
1 3 2

样例输出 #1

4

样例解释 #1

四个不同结果 $[2,3,1]$、$[3,1,2]$、$[2,1,3]$、$[1,3,2]$ 的音高走势都不断转折。

样例输入 #2

4
1 2 3 4

样例输出 #2

0

样例输入 #3

6
3 6 1 5 2 4

样例输出 #3

10

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$25$	$20$
$2$	$75$	$3000$

对于 $100\%$ 的数据，满足 $1 \le n \le 3000$，且 $p$ 是 $1,2,\ldots,n$ 的排列。