[ARC167C] MST on Line++

给定正整数 $n,K$ 和一个长度为 $n$ 的序列 $A$。对于一个 $1\sim n$ 的排列 $P$，我们定义 $f(P)$ 为以下问题的答案： > 给一个 $n$ 个点的无向带权图，对于两点 $i<j$，当且仅当 $j-i\le K$ 时，它们之间有边，边权为 $\max(A_{P_i},A_{P_j})$。 求这个图的最小生成树边权和。 对于所有可能的排列 $P$，求出它们的 $f(P)$ 之和，答案对 $998\,244\,353$ 取模。 $1\le K< N\le 5000$，$1\le A_i \le 10^9$。

[problemUrl]: https://atcoder.jp/contests/arc167/tasks/arc167_c 正整数 $ N,K $ と長さ $ N $ の正整数列 $ A=(A_{1},A_{2},\dots,A_{N}) $ が与えられます。 $ (1,2,\dots\ ,N) $ の順列 $ P=(P_{1},P_{2},\dots\ ,P_{N}) $ に対して以下の「問題 MST on Line」について考え、その答えを $ f(P) $ と書きます。 > **問題 MST on Line** > > 頂点に $ 1 $ から $ N $ までの番号がついた頂点数 $ N $ の重み付き無向グラフ $ G $ があります。$ G $ について $ 1\leq\ i\lt\ j\leq\ N $ を満たす任意の整数の組 $ (i,j) $ に対して以下が成り立ちます。 > > - $ j-i\leq\ K $ ならば頂点 $ i $ と頂点 $ j $ の間に辺が存在して、その辺の重みは **$ \max(A_{P_{i}},A_{P_{j}}) $** > - $ j-i\gt\ K $ ならば頂点 $ i $ と頂点 $ j $ の間に辺は存在しない > > $ G $ の最小全域木の辺の重みの和を求めてください。 全ての $ (1,2,\dots\ ,N) $ の順列 $ P=(P_{1},P_{2},\dots\ ,P_{N}) $ に対する $ f(P) $ の総和を $ 998244353 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ A_{1} $ $ A_{2} $ $ \cdots $ $ A_{N} $

答えを出力してください。

5 2
3 4 5 2 1

1740

2 1
167 924

1848

12 9
22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740

660459584

### 制約 - $ 1\leq\ K\lt\ N\leq\ 5000 $ - $ 1\leq\ A_{i}\leq\ 10^{9} $ - 入力は全て整数 ### Sample Explanation 1 $ P=(1,2,3,4,5) $ としたとき、 頂点 $ 1 $ と $ 2 $ の間に存在する、重み $ 4 $ の辺、 頂点 $ 2 $ と $ 3 $ の間に存在する、重み $ 5 $ の辺、 頂点 $ 2 $ と $ 4 $ の間に存在する、重み $ 4 $ の辺、 頂点 $ 4 $ と $ 5 $ の間に存在する、重み $ 2 $ の辺、 という $ 4 $ つの辺は $ G $ の全域木となり、辺の重みの和は $ 15 $ です。 これ以上辺の重みの和を少なくするように全域木をとることはできないので、$ f(P)=15 $ となります。 以上のように全ての $ (1,2,3,4,5) $ の順列 $ P $ に対する $ f(P) $ の総和を求めると $ 1740 $ になるので、これを出力します。