AT_arc231_e [ARC231E] Odd Inversion

You are given a sequence of positive integers $ A = (A_1, A_2, \cdots, A_N) $ of length $ N $ . Here, $ A_1 \leq A_2 \leq \cdots \leq A_N $ holds. Find the number, modulo $ 998\,244\,353 $ , of possible sequences of positive integers $ B $ of length $ N $ satisfying the following conditions. - $ 1 \leq B_i \leq A_i $ ( $ 1 \leq i \leq N $ ) - The inversion number of $ B $ is odd. Here, the inversion number of $ B $ is the number of pairs of integers $ (i, j) $ satisfying $ 1 \leq i < j \leq N $ such that $ B_i > B_j $ . Solve $ T $ test cases per input file.

The input is given from Standard Input in the following format. Here, $ \mathrm{case}_i $ ( $ 1 \leq i \leq T $ ) denotes the $ i $ -th test case. > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

Output $ T $ lines. The $ i $ -th line ( $ 1 \leq i \leq T $ ) should contain the answer for $ \mathrm{case}_i $ .

### Sample Explanation 1 - For the first test case, $ (2, 1) $ satisfies the conditions. - For the second test case, $ (1, 2, 1), (2, 1, 2), (2, 1, 3) $ satisfy the conditions. ### 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 $ - The sum of $ N $ over the $ T $ test cases is at most $ 400\,000 $ . - All input values are integers.