时间限制：2s

空间限制：512MB

题目描述

有一个长度为 $n$ 的序列 $a$，你需要在里面选出一个波浪形子序列。

所谓“波浪形子序列”的定义是：设该子序列为 $a_{i_1},a_{i_2},\cdots,a_{i_k}$，其中 $1\le i_1<i_2<\cdots<i_k\le n$，则：

• 不存在 $1\le j\le k-1$，使得 $a_{i_j}=a_{i_{j+1}}$；
• 不存在 $1\le j\le k-2$，使得 $a_{i_j}<a_{i_{j+1}}<a_{i_{j+2}}$；
• 不存在 $1\le j\le k-2$，使得 $a_{i_j}>a_{i_{j+1}}>a_{i_{j+2}}$。

对于一个波浪形子序列，定义其权值为这样的 $x$ 的个数：

• 存在 $1\le j\le k-1$，使得 $i_j<x<i_{j+1}$；
• 对于第一条所述的 $j$，$a_{i_j}<x<a_{i_{j+1}}$ 或 $a_{i_j}>x>a_{i_{j+1}}$。

求所有波浪形子序列的权值之和。由于答案很大，请对 $998244353$ 取模。

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行，包含一个整数，表示答案对 $998244353$ 取模后的结果。

样例输入

5
4 2 3 1 5

样例输出

6

数据范围

对于所有数据，保证 $1\le n\le 10^6$，$1\le a_i\le 10^9$。

提示

请注意使用较快的输入方式。