题目背景

观测站每天记录一次气温，日志上密密麻麻排了一整年的数字。研究员想给每个时间段算一个「温差指标」：这段时间里最高气温与最低气温之差。年份太长，他决定先从所有时间段算起。

题目描述

观测记录由 $n$ 天的气温排成一列，第 $i$ 天的气温是整数 $a_i$。

一个时间段指的是一个连续的下标区间 $[l, r]$（$1 \le l \le r \le n$）。这个时间段的温差是 $\max(a_l, \dots, a_r) - \min(a_l, \dots, a_r)$。

请求出所有时间段的温差之和。由于结果可能很大，输出它除以 $998244353$ 的余数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一行一个整数，表示所有时间段温差之和除以 $998244353$ 的余数。

输入输出样例 #1

输入 #1

3
1 3 2

输出 #1

5

输入输出样例 #2

输入 #2

1
5

输出 #2

0

输入输出样例 #3

输入 #3

4
2 2 2 2

输出 #3

0

说明

样例解释

样例 1 中共有 $\dfrac{3 \times 4}{2} = 6$ 个时间段。长度为 $1$ 的三个时间段温差都是 $0$；时间段 $[1,2]$ 的气温是 $1,3$，温差为 $2$；$[2,3]$ 的气温是 $3,2$，温差为 $1$；$[1,3]$ 的最高气温是 $3$、最低气温是 $1$，温差为 $2$。总和 $2 + 1 + 2 = 5$。

样例 2 只有一个时间段（只有一天），温差为 $0$。

样例 3 中所有气温都相同，任何时间段的温差都是 $0$，总和为 $0$。

数据范围

• 对于 $30\%$ 的数据，$n \le 300$；
• 对于 $60\%$ 的数据，$n \le 5000$；
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^{9}$。