Description

Given a sequence $A$ of length $n$, you need to divide the sequence into several intervals (possibly just one). Each interval $[l, r]$ must satisfy the condition that $A_l = A_r$. It is allowed that $l = r$.

Define the contribution of a valid division as the sum of the products of the elements in each non-empty interval. If an interval contains only one element, the product is simply the value of that element.

Compute the sum of contributions of all valid divisions, modulo $998244353$.

Input Format

Two lines in total:

• The first line contains a positive integer $n$, representing the length of the sequence.
• The second line contains $n$ positive integers, representing the sequence $A$.

Output Format

A single line containing one integer — the sum of contributions of all valid divisions modulo $998244353$.

4
1 2 2 1

16

6
1 2 2 1 2 2

104

Hint

Explanation

For the first sample with sequence $\langle 1, 2, 2, 1 \rangle$, there are three valid ways to divide it:

• Divide into $4$ intervals: $[1,1], [2,2], [3,3], [4,4]$, contribution is $1 + 2 + 2 + 1 = 6$.
• Divide into $3$ intervals: $[1,1], [2,3], [4,4]$, contribution is $1 + 2 \times 2 + 1 = 6$.
• Divide into $1$ interval: $[1,4]$, contribution is $1 \times 2 \times 2 \times 1 = 4$.

Total contribution: $6 + 6 + 4 = 16$.

Constraints

Subtasks are used in this problem.

For all test cases, it is guaranteed that $1 \leq n \leq 2.5 \times 10^5$, $1 \leq A_i \leq 40$.