[Solution] Wish I Knew How to Sort Codeforces Solution

E. Wish I Knew How to Sort

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a binary array 𝑎$a$ (all elements of the array are 0$0$ or 1$1$) of length 𝑛$n$. You wish to sort this array, but unfortunately, your algorithms teacher forgot to teach you sorting algorithms. You perform the following operations until 𝑎$a$ is sorted:

1. Choose two random indices 𝑖$i$ and 𝑗$j$ such that 𝑖<𝑗$i<j$. Indices are chosen equally probable among all pairs of indices (𝑖,𝑗)$(i,j)$ such that 1≤𝑖<𝑗≤𝑛$1\le i<j\le n$.
2. If 𝑎𝑖>𝑎𝑗$a_i>a_j$, then swap elements 𝑎𝑖$a_i$ and 𝑎𝑗$a_j$.

What is the expected number of such operations you will perform before the array becomes sorted?

It can be shown that the answer can be expressed as an irreducible fraction 𝑝𝑞$\frac{p}{q}$, where 𝑝$p$ and 𝑞$q$ are integers and 𝑞≢0(mod998244353)$q\not\equiv 0(\mathrm{mod}998244353)$. Output the integer equal to 𝑝⋅𝑞−1mod998244353$p\cdot q^{-1}mod998244353$. In other words, output such an integer 𝑥$x$ that 0≤𝑥<998244353$0\le x<998244353$ and 𝑥⋅𝑞≡𝑝(mod998244353)$x\cdot q\equiv p(\mathrm{mod}998244353)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤105$1\le t\le {10}^5$). Description of the test cases follows.

The first line of each test case contains an integer 𝑛$n$ (1≤𝑛≤200000$1\le n\le 200000$) — the number of elements in the binary array.

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (𝑎𝑖∈{0,1}$a_i\in \{0,1\}$) — elements of the array.

It's guaranteed that sum of 𝑛$n$ over all test cases does not exceed 200000$200000$.

Output

For each test case print one integer — the value 𝑝⋅𝑞−1mod998244353$p\cdot q^{-1}mod998244353$.

Note

Consider the first test case. If the pair of indices (2,3)$(2,3)$ will be chosen, these elements will be swapped and array will become sorted. Otherwise, if one of pairs (1,2)$(1,2)$ or (1,3)$(1,3)$ will be selected, nothing will happen. So, the probability that the array will become sorted after one operation is 13$\frac{1}{3}$, the probability that the array will become sorted after two operations is 23⋅13$\frac{2}{3}\cdot \frac{1}{3}$, the probability that the array will become sorted after three operations is 23⋅23⋅13$\frac{2}{3}\cdot \frac{2}{3}\cdot \frac{1}{3}$ and so on. The expected number of operations is ∑𝑖=1∞(23)𝑖−1⋅13⋅𝑖=3$\sum _{i=1}^{\mathrm{\infty }}{\left(\frac{2}{3}\right)}^{i-1}\cdot \frac{1}{3}\cdot i=3$.

In the second test case the array is already sorted so the expected number of operations is zero.

In the third test case the expected number of operations equals to 754$\frac{75}{4}$ so the answer is 75⋅4−1≡249561107(mod998244353)$75\cdot 4^{-1}\equiv 249561107(\mathrm{mod}998244353)$.