AT_arc228_c [ARC228C] Partially Sort

$ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ が与えられます。 $ (1,2,\dots,N) $ の部分列 $ x=(x_1,x_2,\dots,x_k) $ に対して、以下の手続きによって得られる数列を $ f(x) $ と置きます。 - 数列 $ Q=(Q_1,Q_2,\dots,Q_N) $ を $ Q = P $ で初期化する。 - $ (Q_{x_1},Q_{x_2},\dots,Q_{x_k}) $ を昇順に並び替えて得られる数列を $ A=(A_1,A_2,\dots,A_k) $ と置く。 - $ 1 \le i \le k $ を満たす整数 $ i $ に対して、 $ Q_{x_i} $ を $ A_i $ で置き換える。この時点での $ Q $ を $ f(x) $ とする。 $ x $ として考えられるものは空列も含めて $ 2^N $ 通りありますが、その全てに対する $ f(x) $ の転倒数の総和を $ 998244353 $ で割った余りを求めてください。

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

答えを出力せよ。

### Sample Explanation 1 $ x $ としてあり得る $ 8 $ 通り全てに対する $ f(x) $ とその転倒数は以下のようになります。 - $ x = () $ のとき、 $ f(x) = (3,1,2) $ となり転倒数は $ 2 $ - $ x = (1) $ のとき、 $ f(x) = (3,1,2) $ となり転倒数は $ 2 $ - $ x = (2) $ のとき、 $ f(x) = (3,1,2) $ となり転倒数は $ 2 $ - $ x = (3) $ のとき、 $ f(x) = (3,1,2) $ となり転倒数は $ 2 $ - $ x = (1,2) $ のとき、 $ f(x) = (1,3,2) $ となり転倒数は $ 1 $ - $ x = (1,3) $ のとき、 $ f(x) = (2,1,3) $ となり転倒数は $ 1 $ - $ x = (2,3) $ のとき、 $ f(x) = (3,1,2) $ となり転倒数は $ 2 $ - $ x = (1,2,3) $ のとき、 $ f(x) = (1,2,3) $ となり転倒数は $ 0 $ よって答えは $ 2+2+2+2+1+1+2+0=12 $ です。 ### Constraints - $ 2 \le N \le 2 \times 10^5 $ - $ P $ は $ (1,2,\dots,N) $ の順列 - 入力される値は全て整数