AT_abc221_e [ABC221E] LEQ

题目描述

给定一个长度为 $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$ 取模的结果。

注意，即使两个子序列作为序列内容相同，只要它们选取的下标不同，也视为不同的子序列。

输入格式

输入以以下格式从标准输入给出：

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

输出格式

请输出所有长度不少于 $2$ 的子序列中，满足 $A'_1 \leq A'_k$ 的子序列个数，对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

3
1 2 1

输出 #1

3

输入输出样例 #2

输入 #2

3
1 2 2

输出 #2

4

输入输出样例 #3

输入 #3

3
3 2 1

输出 #3

0

输入输出样例 #4

输入 #4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

输出 #4

830

说明/提示

限制条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入均为整数

样例解释 1

$A = (1,2,1)$ 的所有长度不少于 $2$ 的子序列有 $(1,2)$、$(1,1)$、$(2,1)$、$(1,2,1)$ 共 $4$ 种。其中满足条件的有 $(1,2)$、$(1,1)$、$(1,2,1)$ 共 $3$ 种。

样例解释 2

即使作为序列内容相同，只要选取的下标不同，也视为不同的子序列。在本样例中，满足条件的子序列有 $(1,2)$、$(1,2)$、$(2,2)$、$(1,2,2)$ 共 $4$ 种。

样例解释 3

也有可能不存在满足条件的子序列。

由 ChatGPT 4.1 翻译