Background

I have a inverse pair（逆序对）！

I have a sequence!（区间）！

Awwwwwww......

The sum of the number of inverse pairs of each subsequence（子区间）!

......自从某人被阿露夺舍区域赛打铁两次之后就一直在犯病了。

Description

定义”逆序对“为：在一个数组 $A$ 中，满足 $A_i\gt A_j$ 且 $i\lt j$ 的有序对 $(i,j)$。

定义”本质不同逆序对“为：两个逆序对$(a,b),(c,d)$本质不同，当且仅当 $A_a\neq A_c$ 与 $A_b\neq A_d$ 至少有一个成立。

定义一个序列的子区间序列 $[l,r]$ 为将其第 $l$ 个元素到第 $r$ 个元素取出后按原顺序排序构成的序列。

给定长度为 $n$ 的序列 $A$ ，求其所有子区间序列的本质不同逆序对的数量之和对 $998244353$ 取余数的结果。

Format

Input

输入文件仅两行。

第一行一个正整数 $n$ 表示数组 $a$ 的元素个数。

接下来一行 $n$ 个用空格隔开的正整数，第 $i$ 个数表示 $a_i$。

Output

输出一行一个整数表示答案。

Samples

4
2 1 2 1

5

6
3 2 1 3 2 1

29

15
13 4 9 4 11 1 7 13 6 11 8 5 9 11 9

840

另有三个样例见题目附加文件。

Hints

样例 #1 解释

设 $f(l,r)$ 为 $A$ 的子区间序列 $[l,r]$ 中的本质不同逆序对个数。

$f(1,1)=f(2,2)=f(3,3)=f(4,4)=0,$

$f(1,2)=1,f(1,3)=1,f(1,4)=1,$

$f(2,3)=0,f(2,4)=1,$

$f(3,4)=1$。

Limitations

数据范围

对于全部测试点，满足 $2 \le n \le 5\times 10^5,\forall i\in [1,n]，1\le a_i \le n$。

样例 #4 满足测试点 $7-8$ 的限制。

样例 #5 满足测试点 $11-14$ 的限制。

样例 #6 满足测试点 $15-16$ 的限制。

测试点编号	$n\le$
$1-2$	$10$
$3-4$	$100$
$5-6$	$500$
$7-8$	$2500$
$9-10$	$1.5\times 10^4$
$11-14$	$5\times 10^4$
$15-16$	$2\times 10^5$
$17-20$	$5\times 10^5$