LEQ

题目描述

给定一个长度为 $N$ 的整数序列：$A = (A_1, A_2, \dots, A_N)$。 求满足以下条件的长度至少为 $2$ 的（不必连续的）子序列 $A'=(A'_1,A'_2,\ldots,A'_k)$ 的个数：

$A'_1 \leq A'_k$。

由于计数可能非常大，请对 $998244353$ 取模输出。 这里，当子序列来源于不同的下标集合时，即使作为序列相同，也视为不同的子序列。

输入格式

输入按下述格式由标准输入提供： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出满足题目描述中条件的长度至少为 $2$ 的（不必连续的）子序列 $A'=(A'_1,A'_2,\ldots,A'_k)$ 的个数。

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$ 输入中的所有数值均为整数。$A=(1,2,1)$ 有四个长度至少为 $2$ 的（不必连续的）子序列：$(1,2)$、$(1,1)$、$(2,1)$、$(1,2,1)$。 其中三个，$(1,2)$、$(1,1)$、$(1,2,1)$，满足题目中的条件。
注意，当子序列来源于不同的下标集合时，即使作为序列相同，也视为不同的子序列。 在此样例中，有四个子序列，$(1,2)$、$(1,2)$、$(2,2)$、$(1,2,2)$，满足该条件。
可能不存在满足条件的子序列。

标签: AtCoder|abc221E

来源

AtCoder|abc221E