题目描述

長さ $N$ の整数列 $A\ =\ (A_1,\ A_2,\ \dots,\ A_N)$ が与えられます。

$A$ の連続するとは限らない、長さが $2$ 以上である部分列 $A'=(A'_1,A'_2,\ldots,A'_k)$ のうち以下の条件を満たすものの個数を求めてください。

• $A'_1\ \leq\ A'_k$

なお、この値は非常に大きくなることがあるため、$998244353$ で割ったあまりを出力してください。

ただし、$2$ つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

$A$ の連続するとは限らない、長さが $2$ 以上である部分列のうち問題文中の条件を満たすものの個数を、$998244353$ で割ったあまりを出力せよ。

题目大意

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

求出子序列的总数，使得对于任意的子序列 $A'=(A'_1,A'_2,...,A'_k)$ ，满足 $A'_1 \le A'_k$ 。

答案对 $998244353$ 取模。

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$
• 入力はすべて整数

Sample Explanation 1

$A=(1,2,1)$ の連続するとは限らない、長さが $2$ 以上である部分列は $(1,2)$, $(1,1)$, $(2,1)$, $(1,2,1)$ の $4$ 通りあります。 そのうち問題文中の条件を満たすものは、$(1,2)$, $(1,1)$, $(1,2,1)$ の $3$ 通りです。

Sample Explanation 2

列として同じであっても、取り出す添字が異なる場合 $2$ つの部分列は区別されることに注意してください。 この入出力例において、問題文中の条件を満たすような部分列は $(1,2)$, $(1,2)$, $(2,2)$, $(1,2,2)$ の $4$ 通りです。

Sample Explanation 3

問題文中の条件を満たすような部分列が存在しない場合もあります。