AT_arc219_b [ARC219B] Reverse Permutation

整数 $ N $ と $ (1,2,\ldots,N) $ の順列 $ P=(P_1,P_2,\ldots,P_N) $ が与えられます。 $ (1,2,\ldots,N) $ の順列 $ Q=(Q_1,Q_2,\ldots,Q_N) $ に対して、以下の操作をちょうど $ 1 $ 回行うことにより得られる順列の中で辞書順最小の順列を $ Q'=(Q_1',Q_2',\ldots,Q_N') $ とします： - $ 1\le l\le r\le N $ を満たす整数の組 $ (l,r) $ を選び、 $ Q_l,Q_{l+1},\ldots,Q_r $ を反転させる。より厳密には、 $ Q $ を $ (Q_1,Q_2,\ldots,Q_{l-1} , Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N) $ で置き換える。 $ Q'=P $ となる $ (1,2,\ldots,N) $ の順列 $ Q $ の個数を $ 998244353 $ で割ったあまりを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 例えば $ Q=(2,3,1) $ の場合、 $ (l,r)=(1,3) $ を選ぶことで $ (1,3,2) $ が得られます。 $ (1,3,2) $ より辞書順で小さい順列は得られないので、 $ Q'=(1,3,2) $ となります。したがって、 $ Q=(2,3,1) $ は $ Q'=P $ を満たします。 $ Q'=P $ となる $ Q $ は $ Q=(2,3,1),(3,1,2) $ の $ 2 $ 個です。 ### Constraints - $ 1\le T $ - $ 1\le N\le 5\times 10^5 $ - $ P $ は $ (1,2,\ldots,N) $ の順列 - 全てのテストケースにおける $ N $ の総和は $ 5\times 10^5 $ 以下 - 入力される値は全て整数