P10342 [THUSC 2019] Sequence

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.

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 one integer in the first line, representing the answer modulo $998\ 244\ 353$.

**[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]** | Subtask ID | $n \le$ | $m \le$ | $a_i \le$ | Constraints | Score | | :--: | :--: | :--: | :--: | :--: | :--: | | 1 | $800$ | $800$ | $10^5$ | None | 13 | | 2 | $10^5$ | $10^5$ | $10^5$ | No equal values will appear | 15 | | 3 | $8\times 10^4$ | $600$ | $10^5$ | In $[1,m][m+1,2m]\dots[\lfloor\frac{n}{m}\rfloor\times m + 1,n]$, each interval has no repeated values | 21 | | 4 | $10^5$ | $80$ | $10^5$ | None | 24 | | 5 | $8\times 10^4$ | $600$ | $10^5$ | None | 27 | Translated by ChatGPT 5