首项不超过末项的子序列

题目描述

给你一个长度为 $N$ 的整数序列 $A=(A_1, A_2, \dots, A_N)$。

求满足以下条件的（不一定是连续的）子序列 $A'=(A'_1,A'_2,\ldots,A'_k)$（长度至少为 $2$）的数量：

$A'_1 \le A'_k$。

由于数量可能非常庞大，请对 $998244353$ 取模输出。

这里，即使两个子序列作为序列完全相同，只要它们来自不同的下标集合，就视为不同的子序列。

输入格式

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

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

输出格式

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

样例

3
1 2 1

3

$A=(1,2,1)$ 的长度至少为 $2$ 的（不一定是连续的）子序列共有四个：(1,2)、(1,1)、(2,1)、(1,2,1)。

其中，(1,2)、(1,1)、(1,2,1) 满足题目描述中的条件。

3
1 2 2

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

数据范围

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