P16923 [JLCPC 2026] Crystal Castle.

$\mathit{tarjen}$ is the guardian of the Crystal Castle. In the castle corridor, there is a row of $n$ magic crystals. The color ID of the $i$-th crystal is $a_i$. Adjacent crystals with the same color will resonate and form a **color segment**, which is a maximal contiguous segment of the same color. For example, the color sequence $[1, 1, 2, 2, 1]$ has $3$ color segments: $[1, 1]$, $[2, 2]$, and $[1]$. Every day, travelers come and ask $q$ questions. Each question specifies an interval $[l, r]$: if we take out the crystals in this interval and randomly shuffle them (all different color sequences appear with equal probability), what is the expected number of color segments after shuffling? Output the answer modulo $998244353$. That is, if the answer is the reduced fraction $\dfrac{x}{y}$, output $x \cdot y^{-1} \bmod 998244353$. It can be proven that under the constraints of this problem, $y^{-1}$ always exists.

The first line contains an integer $T$ ($1 \le T \le 10^5$), which is the number of test cases. Then there are $T$ blocks, each describing one test case: - The first line contains two integers $n, q$ ($1 \le n, q \le 10^5$), representing the number of crystals and the number of queries. - The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), representing the color ID of each crystal. - The next $q$ lines each contain two integers $l, r$ ($1 \le l \le r \le n$), representing the endpoints of the query interval. It is guaranteed that $\sum n \le 10^5$ and $\sum q \le 10^5$.

For each query in each test case, output one integer per line, representing the expected number of color segments modulo $998244353$.

For the first sample: For the first query, the taken crystal colors are $[1, 1]$. There is only one permutation, and the number of color segments is $1$. For the second query, the taken crystal colors are $[1, 1, 2, 2]$. The numbers of color segments for the $6$ permutations are $2, 4, 3, 3, 4, 2$, so the expected value is $\dfrac{18}{6} = 3$. Translated by ChatGPT 5