题目描述

给定一个长度为 $N$ 的序列 $A=(A_1,A_2,..., A_N)$。

求出满足要求的子序列的总数。

• 设选出的子序列为 $A'=(A'_1,A'_2,...,A'_k)$ ，满足 $A'_1 \le A'_k$ 。即子序列第一个小于等于最后一个。
• 子序列长度大于等于 $2$。

答案对 $998244353$ 取模。

输入格式

第一行输入一个数字 $n$

接下来一行输入 $n$ 个空格隔开的整数。

输出格式

输出符合要求的子序列个数。

3
1 2 1

3

3
1 2 2

4

3
3 2 1

0

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

830

提示

• $2\ \leq\ N\ \leq\ 3\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力はすべて整数

样例 1 解释

$A=(1,2,1)$ 长度大于等于 $2$ 的子序列有 $4$ 个分别是 $(1,2)$, $(1,1)$, $(2,1)$, $(1,2,1)$ 。 其中 $(2,1)$ 不符合题目的要求。因此答案为 $3$。