Mountain Peaks and Ridges

A sequence \(a\) of length \(m\) (with \(m \ge 3\)) is called a mountain peak if there exists an index \(x\) with \(2 \le x \le m-1\) such that

• \(a_1, a_2, \dots, a_x\) is strictly increasing, and
• \(a_x, a_{x+1}, \dots, a_m\) is strictly decreasing.

In this case, \(a_x\) is called the height of the mountain peak.

A sequence \(b\) is called a mountain ridge if either:

1. \(b\) is a mountain peak, or
2. \(b\) can be split into at least two consecutive segments, each of which is a mountain peak, and the heights of these peaks (from left to right) form a strictly increasing sequence.

Given a sequence \(a\) of length \(n\), count the number of subsequences of \(a\) (two subsequences are considered different if the indices chosen are different) that are mountain ridges. Since the answer may be large, output it modulo \(998244353\).

Note: A subsequence here is obtained by deleting zero or more elements (without changing the order of the remaining elements). When splitting a subsequence \(b\) into segments, the segments must be contiguous in \(b\). Also note that every mountain peak must have at least 3 elements.

inputFormat

The first line contains a single integer \(n\) (the length of the sequence).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer: the number of mountain ridge subsequences modulo \(998244353\).

sample

3
1 3 2

1