# Charlie的云笔记序列

## 题目背景

Charlie 是 oiinhand 的忠实粉丝。他有使用 oih 云笔记记录自己的题解的习惯。只有一点一滴的积累才能留下自己的足迹。

oih 云笔记有什么特点吗？

oih 的站长 soha 表示，目前 oih2 的云笔记功能比较简陋，但是正在开发 oih3 中的新版云笔记功能将是世界上最适合 oier 的储藏笔记的工具。

首先，新版云笔记支持 markdown 功能，并且可以实时预览，插入公式图片都不是问题。实时自动保存，不用担心突然断电啊文档消失，而且不管在哪里都可以看！

其次，可以一键生成题解模板摘要，不用各种复制粘贴了，超省事！

再者，云笔记可以给其他同学分享自己的笔记，共同进步。写完了笔记，还可以一键向洛谷投稿呢！

然而 Charlie 最喜欢的功能是 oih 的题目收藏。现在他收藏了一系列题目，但是觉得不过瘾所以正在玩弄这个功能。

## 题目描述

某天，Charlie 将收藏的题目抽象为一个序列。$a=[a_1,a_2,a_3,\cdots,a_{n-1},a_n]$。

设 $a[l:r]$ 表示序列 ${a_i}$ 第 $l$ 个数到第 $r$ 个数之间的子串，其中 $1 \le l \le r \le n$。形式化地，$a[l:r]={a_l,a_{l+1},a_{l+2},\cdots,a_{r-1},a_r}$。比如说，$a=[9,8,0,3,2,1]$，那么 $a[2:5]=[8,0,3,2]$。

Charlie 对序列 $[a_i]$ 定义了一个函数 $F(l,r)$，表示序列 $a[l:r]$ 的本质不同的子序列个数。特别地，一个空序列也被当作一个本质不同的子序列。

序列 $a[l:r]$ 的子序列定义为 $[a_{i_1},a_{i_2},a_{i_3},\cdots,a_{i_{k-1}},a_{i_k}]$，其中 $l \le i_1<i_2<i3<\cdots<i_{k-1}<i_k \le r$。比如说，$a=[9,8,0,3,2,1]$，那么 $[8,3,2]$ 是 $a[2:5]=[8,0,3,2]$ 的一个子序列。

长度为 $n$ 的序列 $a$ 和长度为 $m$ 的序列 $b$ 被称作本质不同的，当且仅当 $n\neq m$，或存在 $i$，使得 $a_i \neq b_i$。反之，则称这 $2$ 个序列是本质相同的。比如说，$[9,8]$ 和 $[9,7]$ 是本质不同的，$[9,8]$ 和 $[9,8,7]$ 也是本质不同的，而 $[9,8]$ 和 $[9,8]$ 是本质相同的。

举个例子，设 $a=[1,9,9,8,0,3,2,1]$，那么 $F(1,3)=6$，因为 $a[1:3]=[1,9,9]$ 有 $6$ 个子序列：$[],[1],[9],[1,9],[9,9],[1,9,9]$。

现在 Charlie 想知道，$\sum _{1\le l\le r\le n} F(l,r)$ 的值是多少。由于这个数可能很大，请输出它对 $998244353$（$7\times 17\times 2^23+1$，一个质数）取模后的结果。

## 输入格式

第一行一个整数 $n$，表示序列 $a$ 的长度。

第二行包括 $n$ 个整数，表示 $a_1,a_2,a_3,\cdots a_{n-1},a_n$。

## 输出格式

一行，一个整数表示 $\sum _{1\le l\le r\le n} F(l,r)$ 的值对 $998244353$ 取模后的结果。

## 样例 #1

### 样例输入 #1

```
8
1 9 9 8 0 3 2 1
```

### 样例输出 #1

```
814
```

## 提示

- 对于 $10\%$ 的数据，$1\le n \le 10$；
- 对于 $30\%$ 的数据，$1 \le n \le 100$；
- 对于 $50\%$ 的数据，$1\le n \le 1000$，$0 \le a_i \le 10^5$；
- 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$|a_i| \le 10^9$。

oiinhand 3.0 正在开发中。

这将是 oiers 都需要的工具，它不仅集合了全网所有大型 OJ 的资源（题目、题解）而且针对用户还可以将自己在其他 OJ 评测过的代码储存下来，并且有超贴心的云笔记功能，帮助大家最大效率练习。

soha 借此地征求意见，有奖哦！<http://www.wenjuan.com/s/M7fqIv/>