E - LEQ
E - LEQ
分数：500 分
问题描述
给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。
找到长度至少为 $2$ 的子序列 $A'=(A'_1,A'_2,\ldots,A'_k)$ 的个数，满足以下条件：
- $A'_1 \leq A'_k$。
由于计算结果可能很大，答案对 $998244353$ 取模。
注意，即使两个子序列相同，只要它们来自不同的索引集合，它们也是不同的。
约束
- $2 \leq N \leq 3 \times 10^5$
- $1 \leq A_i \leq 10^9$
- 输入中的所有值都是整数。
输入
从标准输入中以以下格式给出：
输出
输出满足问题描述中条件的子序列 $A'=(A'_1,A'_2,\ldots,A'_k)$ 的个数。
3
1 2 1
3
序列 $A=(1,2,1)$ 有 $4$ 个长度至少为 $2$ 的子序列：$(1,2)$, $(1,1)$, $(2,1)$, $(1,2,1)$。
其中有 $3$ 个满足问题描述中的条件：$(1,2)$, $(1,1)$, $(1,2,1)$。
3
1 2 2
4
注意，即使两个子序列相同，只要它们来自不同的索引集合，它们也是不同的。
在该示例中，有 $4$ 个满足条件的子序列：$(1,2)$, $(1,2)$, $(2,2)$, $(1,2,2)$。
3
3 2 1
0
可能没有满足条件的子序列。
10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501
830