There is one tower at each of the points $x = 1, 2, \ldots, N$ on the horizontal axis. The height of the tower at position $x=i$ is $h_i$, and $h_1, h_2, \ldots, h_N$ is a permutation of the integers from $1$ to $N$.

From the top of each tower, that is, from the point $(i,h_i)$, a laser is fired either to the left or to the right with equal probability.

• If the laser is fired to the left, it covers the rectangular region satisfying $0 \le x \le i$ and $0 \le y \le h_i$.
• If the laser is fired to the right, it covers the rectangular region satisfying $i \le x \le N+1$ and $0 \le y \le h_i$.

The directions in which the lasers are fired from all towers are determined independently.

Let $S$ be the area of the union of the regions covered after lasers are fired from all towers. Find the expected value of $2^S$ modulo $998\,244\,353$.

Input

The first line contains the number of towers $N$. ($2 \le N \le 200\,000$)

The second line contains $N$ integers $h_1,h_2,\ldots,h_N$, separated by spaces, representing the heights of the towers. The given heights form a permutation in which each integer from $1$ to $N$ appears exactly once.

Output

Output the expected value of $2^S$ modulo $998\,244\,353$. The number $998\,244\,353$ is prime.

More specifically, the expected value is guaranteed to be a rational number. If it is written as an irreducible fraction $P/Q$, it can be shown that $Q \not\equiv 0 \pmod{998\,244\,353}$. You must output the value of

$$ P \times Q^{-1} \pmod{998\,244\,353}. $$

Examples

Example 1

Input

2
1 2

Output

16

Example 2

Input

3
1 2 3

Output

768

Example 3

Input

6
6 5 2 3 4 1

Output

448265500

Note

In Example 1, the entire space ranges from $x=0$ to $x=3$. For the four possible combinations of directions in which towers $1$ and $2$ fire their lasers, the area $S$ of the union of the covered regions and the value of $2^S$ are as follows. Each case occurs with probability $1/4$.

• Left, left: The interval $0 \le x \le 2$ is covered up to height $2$. ($S=4$, $2^S=16$)
• Left, right: The interval $0 \le x \le 1$ is covered up to height $1$, and the interval $2 \le x \le 3$ is covered up to height $2$. ($S=3$, $2^S=8$)
• Right, left: The interval $0 \le x \le 2$ is covered up to height $2$, and the interval $2 \le x \le 3$ is covered up to height $1$. ($S=5$, $2^S=32$)
• Right, right: The interval $1 \le x \le 2$ is covered up to height $1$, and the interval $2 \le x \le 3$ is covered up to height $2$. ($S=3$, $2^S=8$)

Therefore, the expected value of $2^S$ is

$$ \frac{16+8+32+8}{4}=16. $$