AT_arc228_c [ARC228C] Partially Sort

You are given a permutation $ P=(P_1,P_2,\dots,P_N) $ of $ (1,2,\dots,N) $ . For a subsequence $ x=(x_1,x_2,\dots,x_k) $ of $ (1,2,\dots,N) $ , let $ f(x) $ denote the sequence obtained by the following procedure. - Initialize the sequence $ Q=(Q_1,Q_2,\dots,Q_N) $ with $ Q = P $ . - Let $ A=(A_1,A_2,\dots,A_k) $ be the sequence obtained by sorting $ (Q_{x_1},Q_{x_2},\dots,Q_{x_k}) $ in ascending order. - For every integer $ i $ satisfying $ 1 \le i \le k $ , replace $ Q_{x_i} $ with $ A_i $ . Let $ f(x) $ be $ Q $ at this point. There are $ 2^N $ possible choices of $ x $ , including the empty sequence. Find the sum, modulo $ 998244353 $ , of the number of inversions of $ f(x) $ over all those choices.

The input is given from Standard Input in the following format: > $ N $ $ P_1\ P_2\ \dots\ P_N $

Output the answer.

### Sample Explanation 1 $ f(x) $ and its number of inversions for all eight possible choices of $ x $ are as follows. - For $ x = () $ , we have $ f(x) = (3,1,2) $ , and the number of inversions is $ 2 $ . - For $ x = (1) $ , we have $ f(x) = (3,1,2) $ , and the number of inversions is $ 2 $ . - For $ x = (2) $ , we have $ f(x) = (3,1,2) $ , and the number of inversions is $ 2 $ . - For $ x = (3) $ , we have $ f(x) = (3,1,2) $ , and the number of inversions is $ 2 $ . - For $ x = (1,2) $ , we have $ f(x) = (1,3,2) $ , and the number of inversions is $ 1 $ . - For $ x = (1,3) $ , we have $ f(x) = (2,1,3) $ , and the number of inversions is $ 1 $ . - For $ x = (2,3) $ , we have $ f(x) = (3,1,2) $ , and the number of inversions is $ 2 $ . - For $ x = (1,2,3) $ , we have $ f(x) = (1,2,3) $ , and the number of inversions is $ 0 $ . Thus, the answer is $ 2+2+2+2+1+1+2+0=12 $ . ### Constraints - $ 2 \le N \le 2 \times 10^5 $ - $ P $ is a permutation of $ (1,2,\dots,N) $ . - All input values are integers.