Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
H. Subarray
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$, we say a continuous subarray $$$a_l, a_{l + 1}, \cdots, a_r$$$ is good, if the maximum element of the subarray appears exactly $$$k$$$ times in the subarray. For each $$$1 \le k \le n$$$, count the number of good subarrays.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 4 \times 10^5$$$) indicating the length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) indicating the sequence.

It's guaranteed that the sum of $$$n$$$ of all test cases does not exceed $$$4 \times 10^5$$$.

Output

Let $$$c_i$$$ be the number of good subarrays when $$$k = i$$$. To decrease the size of output, for each test case, just output one line containing one integer indicating $$$\sum\limits_{i = 1}^n (i \times c_i^2)$$$ modulo $$$998244353$$$.

Example
Input
3
11
1 1 2 1 2 2 3 3 2 3 1
3
2024 5 26
3
1000000000 1000000000 1000000000
Output
2564
36
20
Note

We denote $$$[l, r]$$$ as the continuous subarray $$$a_l, a_{l + 1}, \cdots, a_r$$$. For the first sample test case:

  • $$$c_1 = 27$$$, $$$c_2 = 22$$$ and $$$c_3 = 17$$$, while $$$c_4, c_5, \cdots, c_{11}$$$ are all $$$0$$$. So the answer is $$$(1 \times 27^2 + 2 \times 22^2 + 3 \times 17^2) \bmod 998244353 = 2564$$$.
  • Some examples of good subarrays when $$$k = 1$$$ are $$$[3, 3]$$$ (maximum element $$$2$$$ appears once), $$$[4, 5]$$$ (maximum element $$$2$$$ appears once), and $$$[9, 10]$$$ (maximum element $$$3$$$ appears once).
  • Some examples of good subarrays when $$$k = 2$$$ are $$$[1, 2]$$$ (maximum element $$$1$$$ appears twice), $$$[4, 6]$$$ (maximum element $$$2$$$ appears twice), and $$$[6, 9]$$$ (maximum element $$$3$$$ appears twice).
  • Some examples of good subarrays when $$$k = 3$$$ are $$$[3, 6]$$$ (maximum element $$$2$$$ appears three times), $$$[2, 6]$$$ (maximum element $$$2$$$ appears three times), and $$$[1, 11]$$$ (maximum element $$$3$$$ appears three times).