配点 : $500$ 点

問題文

長さ $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$ つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。

制約

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

入力

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

$N$

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

出力

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

3
1 2 1

3

$A=(1,2,1)$ の連続するとは限らない、長さが $2$ 以上である部分列は $(1,2)$, $(1,1)$, $(2,1)$, $(1,2,1)$ の $4$ 通りあります。

そのうち問題文中の条件を満たすものは、$(1,2)$, $(1,1)$, $(1,2,1)$ の $3$ 通りです。

3
1 2 2

4

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

この入出力例において、問題文中の条件を満たすような部分列は $(1,2)$, $(1,2)$, $(2,2)$, $(1,2,2)$ の $4$ 通りです。

3
3 2 1

0

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

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

830