题目描述

给定长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，称一个连续子数组 $a_l, a_{l + 1}, \cdots, a_r$ 是好的，若子数组里的最大元素在子数组里恰好出现了 $k$ 次。对每个 $1 \le k \le n$ 计算好的子数组的数量。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 4 \times 10^5$）表示序列的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^9$）表示序列。

保证所有数据 $n$ 之和不超过 $4 \times 10^5$。

输出格式

令 $c_i$ 表示 $k = i$ 时好的子数组的数量。为了减少输出的大小，每组数据只需要输出一行一个整数，表示 $\sum\limits_{i = 1}^n (i \times c_i^2)$ 对 $998244353$ 取模的结果。

3
11
1 1 2 1 2 2 3 3 2 3 1
3
2024 5 26
3
1000000000 1000000000 1000000000

2564
36
20

提示

令 $[l, r]$ 表示连续子数组 $a_l, a_{l + 1}, \cdots, a_r$。对于第一组样例数据：

• $c_1 = 27$，$c_2 = 22$，$c_3 = 17$，而 $c_4, c_5, \cdots, c_{11}$ 均为 $0$。所以答案为 $(1 \times 27^2 + 2 \times 22^2 + 3 \times 17^2) \bmod 998244353 = 2564$。
• 当 $k = 1$ 时，一些好的子数组的例子有 $[3, 3]$（最大元素 $2$ 出现了一次），$[4, 5]$（最大元素 $2$ 出现了一次），以及 $[9, 10]$（最大元素 $3$ 出现了一次）。
• 当 $k = 2$ 时，一些好的子数组的例子有 $[1, 2]$（最大元素 $1$ 出现了两次），$[4, 6]$（最大元素 $2$ 出现了两次），以及 $[6, 9]$（最大元素 $3$ 出现了两次）。
• 当 $k = 3$ 时，一些好的子数组的例子有 $[3, 6]$（最大元素 $2$ 出现了三次），$[2, 6]$（最大元素 $2$ 出现了三次），以及 $[1, 11]$（最大元素 $3$ 出现了三次）。