K-52Hz的minmax区间（hard）_第五届武汉纺织大学ACM程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一个排列
1.定义 $p_{max}(l,r)$ 为下标为l到r区间内最大值所在的下标
2.定义 $p_{min}(l,r)$ 为下标为l到r区间内最小值所在的下标
3.定义 $f(l,r)=|p_{max}(l,r)-p_{min}(l,r)|$
求 $\sum_{i=1}^{n}\sum_{j=1}^{i}f(j,i)$

输入描述:

第一行输入一个数n表示排列的长度 n 
第二行输入n个数，表示下标为 i 的排列的值

输出描述:

输出一个数表示答案
由于答案可能过大，请输出模998244353的答案

示例1

输入

复制

5
5 2 4 3 1

输出

复制