Mizuhashi Parsee has two hobbies. One is writing descriptions unrelated to the title, and the other is creating complex histogram problems.

You are given a histogram consisting of $N$ bars. Each bar in the histogram has width $1$, and the height of the $i$-th bar from the left is $H_i$.

For three positive integers $1 \le L \le R \le N, 1 \le K \le 10^9$, define $f(L,R,K)$ as the answer to the following problem:

• Considering only the histogram between the $L$-th and $R$-th bars (inclusive), find the maximum width of a rectangle of height $K$ contained in this histogram.

You are required to compute $\sum_{L=1}^N \sum_{R=L}^N \sum_{K=1}^{10^9} f(L,R,K)$ modulo $998,244,353$.

Constraints

• $2 \le N \le 2^{17}$
• For all $1\le i\le N$, $1\le H_i\le 10^9$

Subtasks

1. (9 points) $N\le 50, \max_{i=1}^N H_i\le 50$.

2. (8 points) $N\le 2^7$.

3. (8 points) $N\le 2^8$.

4. (9 points) $N\le 2^9$.

5. (8 points) $N\le 2^{10}$.

6. (8 points) $N\le 2^{11}$.

7. (8 points) $N\le 2^{12}$.

8. (9 points) $N\le 2^{13}$.

9. (8 points) $N\le 2^{14}$.

10. (8 points) $N\le 2^{15}$.

11. (8 points) $N\le 2^{16}$.

12. (9 points) No additional constraints.

Input

The first line contains a positive integer $N$.

The second line contains $N$ integers $H_1, H_2, \cdots, H_N$ separated by spaces.

Output

Output $\sum_{L=1}^N \sum_{R=L}^N \sum_{K=1}^{10^9} f(L,R,K)$ modulo $998,244,353$.

Example

Example 1

Input

10
6 4 10 8 5 8 6 1 7 2

Output

1148