Problem Description

Define the value of a sequence of length $k$ as: $val = \max \limits_{1 \le i \le k}\{i \times f(i,k)\}$.

Here, $f(i,j)$ denotes the number of distinct values within the interval $[i,j]$.

Given a sequence of length $n$, compute the sum of values over all contiguous subintervals. Treat each contiguous subinterval as an independent sequence; the computed value is exactly the value of that subinterval.

Let $m$ be the number of distinct values appearing in the sequence.

Input Format

The first line contains an integer $n$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, describing the value at each position of the sequence.

For all input data, it holds that $1 \le n \le 10^5$.

Output Format

Output one integer in the first line, representing the answer modulo $998\ 244\ 353$.

4
12 23 23 45

23

Hint

[Sample Explanation 1]

All intervals of length $1$ contribute $1$ to the answer.

All intervals of length $2$ contribute $2$ to the answer.

The interval $[1,3]$ contributes $3$ to the answer.

The interval $[2,4]$ contributes $4$ to the answer.

The interval $[1,4]$ contributes $6$ to the answer.

Therefore, the answer is $ans = 4 \times 1 + 2 \times 3 + 3 + 4 + 6 = 23$.

[Sample 2]

See the attached files 2.in/ans.

[Sample 3]

See the attached files 3.in/ans.

[Sample 4]

See the attached files 4.in/ans.

[Sample 5]

See the attached files 5.in/ans.

[Subtasks]

Translated by ChatGPT 5