시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 0 | 0 | 0 | 0.000% |
You are given an integer array $a_1, \ldots, a_n$. A subsegment of even length $a_i,\ldots, a_{i + 2m - 1}$ is called good if $\left|\max(a_i,\dots, a_{i + m - 1}) - \max(a_{i + m}, \ldots, a_{i + 2m - 1})\right| \leq k$.
Let us define an integer sequence $f$ as follows:
Calculate the sum $(a_{i+m-1} + 10) \cdot f_{m}$ among all good subsegments. Since this number can be large, print it modulo $998\,244\,353$.
The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) --- the number of test cases. Description of test cases follows.
The first line of each test case contains two integers $n$, $k$ ($1 \leq n \leq 5 \cdot 10^5$, $0 \leq k \leq \min (n, 10)$).
The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).
It is guaranteed that the sum of $n$ for all test cases does not exceed $5 \cdot 10^5$.
For each test case, print a single integer --- the answer to the problem.
3 6 0 3 1 3 1 3 1 8 4 5 8 4 6 5 7 8 5 7 3 2 1 3 2 2 1 3
144768 745933 448953