Description

One day, Charlie abstracts his collected problems into a sequence. $a = [a_1, a_2, a_3, \cdots, a_{n-1}, a_n]$.

Let $a[l:r]$ denote the subarray of the sequence $\{a_i\}$ from the $l$-th element to the $r$-th element, where $1 \le l \le r \le n$. Formally, $a[l:r] = \{a_l, a_{l+1}, a_{l+2}, \cdots, a_{r-1}, a_r\}$. For example, if $a = [9, 8, 0, 3, 2, 1]$, then $a[2:5] = [8, 0, 3, 2]$.

Charlie defines a function $F(l, r)$ on the sequence $[a_i]$, which denotes the number of essentially different subsequences of $a[l:r]$. In particular, the empty sequence is also counted as one essentially different subsequence.

A subsequence of $a[l:r]$ is defined as $[a_{i_1}, a_{i_2}, a_{i_3}, \cdots, a_{i_{k-1}}, a_{i_k}]$, where $l \le i_1 < i_2 < i_3 < \cdots < i_{k-1} < i_k \le r$. For example, if $a = [9, 8, 0, 3, 2, 1]$, then $[8, 3, 2]$ is a subsequence of $a[2:5] = [8, 0, 3, 2]$.

A sequence $a$ of length $n$ and a sequence $b$ of length $m$ are called essentially different if and only if $n \ne m$, or there exists $i$ such that $a_i \ne b_i$. Otherwise, the two sequences are called essentially the same. For example, $[9, 8]$ and $[9, 7]$ are essentially different; $[9, 8]$ and $[9, 8, 7]$ are also essentially different; while $[9, 8]$ and $[9, 8]$ are essentially the same.

For example, let $a = [1, 9, 9, 8, 0, 3, 2, 1]$. Then $F(1, 3) = 6$, because $a[1:3] = [1, 9, 9]$ has $6$ subsequences: $[], [1], [9], [1, 9], [9, 9], [1, 9, 9]$.

Now Charlie wants to know the value of $\sum_{1 \le l \le r \le n} F(l, r)$. Since this number may be large, please output it modulo $998244353$ ($7 \times 17 \times 2^{23} + 1$, a prime).

Input Format

The first line contains an integer $n$, denoting the length of the sequence $a$.

The second line contains $n$ integers, denoting $a_1, a_2, a_3, \cdots, a_{n-1}, a_n$.

Output Format

One line containing a single integer: the value of $\sum_{1 \le l \le r \le n} F(l, r)$ modulo $998244353$.

8
1 9 9 8 0 3 2 1

814

Hint

• For $10\%$ of the testdata, $1 \le n \le 10$.
• For $30\%$ of the testdata, $1 \le n \le 100$.
• For $50\%$ of the testdata, $1 \le n \le 1000$, $0 \le a_i \le 10^5$.
• For $100\%$ of the testdata, $1 \le n \le 10^5$, $|a_i| \le 10^9$.

oiinhand 3.0 is under development.

This will be a must-have tool for OIers. It not only aggregates resources (problems, solutions) from all major OJs across the web, but also allows users to store code they have been judged on other OJs, and it has a very considerate cloud notes feature to help everyone practice with maximum efficiency.

soha is soliciting feedback here, with rewards! http://www.wenjuan.com/s/M7fqIv/

Translated by ChatGPT 5