Background

Charlie is a loyal fan of oiinhand. He has the habit of using oih cloud notes to record his problem solutions. Only bit-by-bit accumulation can leave his own footprints.

Does oih cloud notes have any special features?

oih’s admin soha says that the current cloud notes in oih2 are relatively simple, but the new cloud notes under development for oih3 will be the best tool in the world for OIers to store their notes.

First, the new cloud notes support Markdown with real-time preview; inserting formulas and images is not a problem. It saves automatically in real time, so you do not need to worry about sudden power outages or document loss, and you can view it anywhere!

Second, it can generate a problem-solution template summary with one click, so you no longer need to copy and paste. Super convenient!

Moreover, cloud notes can be shared with other classmates for mutual improvement. After finishing a note, you can submit it to Luogu with one click!

However, Charlie’s favorite feature is oih’s problem collection. He has now collected a series of problems, but he feels it is not enough, so he is playing with this feature.

Problem 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