题目描述

定义一个值域为 $[1,n]$，长度分别为 $k,n$ 的数组对 $(a,p)$ 是好的，当且仅当：

• $\forall 1\leq i\leq k, a_{k-i+1} = p_{a_i}$。

给你一个值域为 $[1,n]$，长度为 $n$ 的数组 $a$，对于 $a$ 的 $\frac{n(n+1)}2$ 个子段 $a'$，以及 $n^n$ 个值域为 $[1,n]$，长度为 $n$ 的数组 $p$，求出好的数组对 $(a',p)$ 数量，对 $998244353$ 取模。

输入格式

第一行为一个正整数 $n$，第二行 $n$ 个数为数组 $a$。

输出格式

一行一个整数，代表好的数组对数对 $998244353$ 取模的结果。

样例输入 1

3
1 1 2

样例输出 1

39

样例输入 2

5
1 4 2 2 1

样例输出 2

4175

样例解释

对于第一个样例：

• 有两个子段为 $a'=[1]$，其有 $9$ 个对应的好的 $p$。
• 有一个子段为 $a'=[2]$，其有 $9$ 个对应的好的 $p$。
• 有一个子段为 $a'=[1,1]$，其有 $9$ 个对应的好的 $p$。
• 有一个子段为 $a'=[1,2]$，其有 $3$ 个对应的好的 $p$。
• 有一个子段为 $a'=[1,1,2]$，其有 $0$ 个对应的好的 $p$。

总共有 $2\times9+9+9+3+0=39$ 个好的数组对 $(a',p)$。

数据范围

对于所有数据，

• $1\leq n\leq 10^6$，
• $\forall 1\leq i\leq n$，$1\leq a_i\leq n$。

• 特殊性质 A：$\forall 1\leq i\leq n$，$a_i=i$。

2s / 2048MB