AT_arc167_c [ARC167C] MST on Line++

[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} $

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

### 制約 - $ 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 $ になるので、これを出力します。