U250767 【D&S R1-2】福瑞会得奇蹄病吗
题目背景
兽圈承诺绝不交易奇蹄病病毒制剂（鞠躬。）。我们也~~不会去找~~不知道 _dado_ 是谁（再次鞠躬。）。
题目描述
现有一个 $1$ 至 $n$ 的排列 $p$，求：
$$
\sum_{1\leq a\leq b\leq n} F(a,b)
$$
$F(a,b)$ 的值为将排列 $p$ 中下标区间 $[a,b]$ 中的所有数建成一棵大根[笛卡尔树](https://oi-wiki.org/ds/cartesian-tree/)（即父亲节点的权值大于左右儿子权值）后所有节点的权值与其深度之积的和（根节点深度为 $1$）。
答案对 $998244353$ 取模。
输入格式
第一行一个整数 $n$。
以下一行 $n$ 个整数，表示排列 $p$。
输出格式
输出一个整数代表答案。
答案对 $998244353$ 取模。
说明/提示
【样例解释 1】
这里以算 $F(1,5)$ 为例：
笛卡尔树第一层，是 $5$，对答案贡献为 $5\times 1=5$。
笛卡尔树第二层，是 $4,3$，对答案贡献为 $4\times 2+3\times 2=14$。
笛卡尔树第三层，是 $1,2$，对答案贡献为 $1\times 3+2\times 3=9$。
所以 $F(1,5)=5+14+9=28$。
---
【数据范围与提示】
**本题采用捆绑测试。**
| Subtask 编号 | $n$ | 特殊性质 | 分数 |
| :-----------: | :-----------: |:-----------: |:-----------: |
| $1$ | $\leq 300$ | - | $15$ |
| $2$ | $\leq 10^4$ | $p$ 是单调的| $5$ |
| $3$ |$\leq 10^4$| - | $30$ |
| $4$ |$\leq 10^6$| - | $50$ |
对于 $100\%$ 的数据，$1\leq n\leq 10^6$。