← 返回题目列表

AtCoder · abc221_e

H. 小于等于

中文机器翻译题面 查看原题

分数: 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