题目描述

给定一个由 $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$
• 输入中的所有值都是整数。

---

输入

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

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

输出

打印满足问题描述中条件的长度至少为 $2$ 的子序列 $A'=(A'_1,A'_2,\\ldots,A'_k)$ 的数量。

---

示例输入 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