P12674 「LAOI-8」Count

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$.

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$.

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

### 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.** | Subtask | Constraint on $n$ | Constraint on $A_i$ | Score | | :-----: | :------------------------: | :--------------------: | :---: | | $1$ | $n \leq 10$ | $A_i \leq 3$ | $10$ | | $2$ | $n \leq 10^3$ | $A_i \leq 40$ | $20$ | | $3$ | $n \leq 2.5 \times 10^5$ | $A_i \leq 2$ | $30$ | | $4$ | $n \leq 2.5 \times 10^5$ | $A_i \leq 40$ | $40$ | For all test cases, it is guaranteed that $1 \leq n \leq 2.5 \times 10^5$, $1 \leq A_i \leq 40$.