题目背景

English statement. You must submit your code at the Chinese version of the statement.

山峦是造物主弃的酒杯。

题目描述

如果一个长度至少为三的序列 $a$ 满足以下条件，则称其为一个山峰：

• 设其长度为 $m$。存在一个 $x$，满足 $2\leq x \leq m-1$，并且使得 $a_1,a_2,\cdots,a_x$ 严格单调递增，$a_x,a_{x+1},\cdots,a_m$ 严格单调递减。

特别地，称 $a_x$ 为这个山峰的高度。

如果一个序列 $b$ 满足以下任一条件，则称其为一个山峦：

• $b$ 序列是一个山峰。

• 可以拆成至少两个连续的子序列，使得每个子序列都是山峰，且从左到右山峰的高度严格单调递增。

比如，序列 $\lbrace 2,4,3,1,5,2,1 \rbrace$ 是山峦，因为其可以拆分为 $\lbrace 2,4,3 \rbrace,\lbrace 1,5,2,1 \rbrace$ 两个山峰，且山峰高度严格递增。而序列 $\lbrace 2,4,3,5,2,1 \rbrace$ 不是山峦，因为其无法拆分成至少两个连续的子序列，使得每个子序列都是山峰。

现在给定一个长度为 $n$ 的序列 $a$，小 F 想知道，在 $a$ 的所有子序列中，有多少个是山峦。由于答案可能很大，请输出其对 $998244353$ 取余后的结果。

请注意，在本题中，即使子序列的元素相同，只要子序列的元素在 $a$ 中的位置不同，仍算作不同的子序列。

输入格式

共两行。

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示 $a$ 序列。

输出格式

共一行。

一个整数，表示是山峦的子序列数量对 $998244353$ 取余的结果。

4
1 2 2 1

2

7
2 4 3 1 5 2 1

35

20
2 3 5 6 8 7 6 5 6 7 8 8 8 8 4 3 5 6 7 4

15085

提示

【样例 1 解释】

由 $a_1,a_2,a_4$ 构成的子序列是山峦，由 $a_1,a_3,a_4$ 构成的子序列是山峦。

【数据规模与约定】

本题采用捆绑测试。

对于 $100 \%$ 的数据，保证：

• $1 \leq n \leq 500$
• $1 \leq a_i \leq 10^6$

子任务	分值	特殊性质
$1$	$10$	$n \leq 18$
$2$	$15$	$n \leq 80$
$3$		$A$
$4$	$20$	$B$
$5$	$40$	无

特殊性质 $A$：序列 $a$ 是山峰。

特殊性质 $B$：序列 $a$ 中的元素互不相同。