分数: 500 点
问题陈述
给定的是一系列 N 整数: A = (A_1, A_2, \dots, A_N).
查找(不一定是连续的)子序列的数量 长度至少为 A'=(A'_1,A'_2,\ldots,A'_k) 至少长度 2 满足以下条件:
- A'_1 \leq A'_k.
由于计数可能很大,因此将其模数打印出来 998244353.
这里,当两个子序列源自不同的索引集时,即使它们与序列相同,它们也会被区分。
约束
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印(不一定是连续的)子序列的数量 A'=(A'_1,A'_2,\ldots,A'_k) 至少长度 2 满足问题陈述中的条件。
示例输入 1
3 1 2 1
示例输出 1
3
A=(1,2,1) 至少有四个(不一定是连续的)长度子序列 2: (1,2), (1,1), (2,1), (1,2,1).
其中三个, (1,2), (1,1), (1,2,1),满足问题陈述中的条件。
示例输入 2
3 1 2 2
示例输出 2
4
请注意,当两个子序列源自不同的索引集时,即使它们与序列相同,它们也会被区分。
在此示例中,有四个子序列, (1,2), (1,2), (2,2), (1,2,2),满足条件。
示例输入 3
3 3 2 1
示例输出 3
0
可能没有满足条件的子序列。
示例输入 4
10 198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501
示例输出 4
830