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

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/>