AT_pakencamp_2021_day2_m Deque and Inversions

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day2/tasks/pakencamp_2021_day2_m 正の整数 $ N $ が与えられます。Natsubi くんは、空の数列 $ Q $ を用意したうえで、$ (1,2,\dots,N) $ を並び替えた数列 $ P=(P_1,\ P_2,\ \dots,\ P_N) $ を自由に選んで、以下の一連の操作を $ N $ 回行います。 1. $ P $ の先頭の要素を $ x $ として、$ Q $ の先頭または末尾に $ x $ を追加する。 2. $ P $ から $ x $ を削除する。 Natsubi くんは、最終的な $ Q $ の転倒数が最小となるように適切に操作を行います。 $ P $ として考えられるものは $ N! $ 通りありますが、それらすべてについて操作後の $ Q $ の転倒数の最小値を求め、その総和を $ 998244353 $ で割ったあまりを出力してください。 転倒数とは？$ (1,2,\dots,N) $ を並び替えた数列 $ P'=(P'_1,\ P'_2,\ \dots,\ P'_N) $ に対する転倒数は、$ 1\ \leq\ i\ なる整数\ i,j $ の組であって、$ P'_i\ >\ P'_j $ を満たすものの個数のことを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $

答えを $ 1 $ 行に出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 3\ \times\ 10^5 $ - 入力は全て整数 ### Sample Explanation 1 例えば、$ P=(3,2,1,4) $ のとき、適切に操作を行うことで $ Q=(1,2,3,4) $ とすることができ、転倒数は $ 0 $ となります。 他の $ P $ についても同様に計算すると、答えは $ 20 $ であることが分かります。 ### Sample Explanation 2 原案: \[NatsubiSogan\](https://atcoder.jp/users/NatsubiSogan)