Given is a sequence $A$ of $N$ numbers.
There are $2^{N-1}$ ways to divide $A$ into non-empty contiguous subsequences $B_1,B_2,\ldots,B_k$. Find the value below for each of those ways, and print the sum, modulo $998244353$, of those values.

• $\prod_{i=1}^{k} (\max(B_i)-\min(B_i))$

Here, for a sequence $B_i=(B_{i,1},B_{i,2},\ldots,B_{i,j}), \max(B_i)$ and $\min(B_i)$ are defined to be the maximum and minimum values of an element of $B_i$, respectively.

Input is given from Standard Input in the following format:
$N$
$A_1\ A_2\ \dots\ A_N$

Print the sum, modulo $998244353$, of the values found.

$1≤N≤3×10^5$
$1 \leq A_i \leq 10^9$
All values in input are integers.

2

There are $4$ ways to divide $A=(1,2,3)$ into non-empty contiguous subsequences, as follows.

• $(1), (2), (3)$
• $(1), (2,3)$
• $(1,2), (3)$
• $(1,2,3)$

$\prod_{i=1}^{k} (\max(B_i)-\min(B_i))$ for these divisions are $0, 0, 0, 2$, respectively. The sum of them, $2$, should be printed.