AT_arc231_e [ARC231E] Odd Inversion

長さが $ N $ の正整数列 $ A = (A_1, A_2, \cdots, A_N) $ が与えられます．ここで， $ A_1 \leq A_2 \leq \cdots \leq A_N $ が成立します． 以下の条件を満たす長さが $ N $ の正整数列 $ B $ としてありうる個数を $ 998\,244\,353 $ で割ったあまりを求めてください． - $ 1 \leq B_i \leq A_i $ ( $ 1 \leq i \leq N $ ) - $ B $ の転倒数は奇数 ここで， $ B $ の転倒数とは $ 1 \leq i < j \leq N $ を満たす整数の組 $ (i, j) $ で $ B_i > B_j $ であるものの個数を表します． $ 1 $ つの入力ファイルにつき， $ T $ 個のテストケースを解いてください．

入力は以下の形式で標準入力から与えられる．ここで， $ \mathrm{case}_i $ ( $ 1 \leq i \leq T $ ) は $ i $ 番目のテストケースを意味する． > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

$ T $ 行出力せよ． $ i $ 行目 ( $ 1 \leq i \leq T $ ) には $ \mathrm{case}_i $ に対する答えを出力せよ．

### Sample Explanation 1 - $ 1 $ 番目のテストケースについて， $ (2, 1) $ が条件を満たします． - $ 2 $ 番目のテストケースについて， $ (1, 2, 1), (2, 1, 2), (2, 1, 3) $ が条件を満たします． ### Constraints - $ 1 \leq T \leq 10\,000 $ - $ 1 \leq N \leq 200\,000 $ - $ 1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9 $ - $ T $ 個のテストケースにおける $ N $ の総和は $ 400\,000 $ 以下 - 入力される値はすべて整数である