Description

Kirara 发现，如果存在一段连续的魔法区间 $[l, r]$，其中魔法能量的最小值大于她起点 $a_x$ 和终点 $a_y$ 的能量，那么她就能安全地从 $x$ 移动到 $y$，中间受到保护。这段区间就像“風に包まれてく”（被风包围）一样，提供庇护。否则，她可能会被森林中的魔法吞噬。

现在，Kirara 需要你的帮助：给定森林中 $n$ 个节点的魔法能量 $a_i$，找出所有满足条件的四元组 $(x, l, r, y)$，并统计其数量，其中 $1 \le x<l \le r<y \le n$，且 $a$ 的区间 $[l, r]$ 上的最小魔法能量大于你所选择的起点 $a_x$ 和你所选择的终点 $a_y$ 的能量。这样，她就能识别所有安全路径，踏上“果てしのない旅”（无尽的旅程），寻找逃脱的希望。

由于答案可能很大，你只需要给出满足条件的四元组数量对 $998244353$ 取模的值。

Input Format

第一行一个整数 $n\ (3\le n\le 3\times10^5)$，表示魔法结点的数量。

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i\ (1\le a_i\le n)$，表示第 $i$ 个节点的魔法能量。

Output Format

一个非负整数，表示满足条件的四元组数量。答案对 $998244353$ 取模。

5
3 5 4 3 2

7

10
1 1 1 2 1 1 1 2 1 1

27

Hint

对于第一组输入样例，一共有 $7$ 个四元组满足条件：$(1, 2, 2, 3)$，$(1, 2, 2, 4)$，$(1, 2, 2, 5)$，$(1, 2, 3, 4)$，$(1, 2, 3, 5)$，$(1, 3, 3, 4)$，$(1, 3, 3, 5)$。

帮助 Kirara 找到所有这样的 $(x, l, r, y)$ 路径，让她实现约定，逃离森林吧！