#4 ビル跳び

難易度

## 問題 $N$個のビルがあり、左から右に一直線に並んでいます。左から$i(1 \le i \le N)$番目のビルをビル$i$と呼ぶことにし、その高さは$A_i$です。 以下に従ってクエリを$Q$個処理してください。 - クエリ : $i$番目のクエリでは$L_i, R_i$が与えられるのでビル$L_i$からビル$R_i$まで以下を繰り返して移動する際に払う金額として考えられる最小値を求めてください。 - 今より$1$個以上$K$個以下右に存在するビルに移動する。この時2つのビルの高さの差の絶対値の金額だけ払う。 ## 入力 $N \hspace{7pt} K$ $A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N$ $Q$ $L_1 \hspace{7pt} R_1$ $L_2 \hspace{7pt} R_2$ $L_3 \hspace{7pt} R_3$ $\hspace{13pt} \vdots$ $L_Q \hspace{7pt} R_Q$ ## 制約 $1 \le K \lt N \le 10^5$ $K \le 100$ $0 \le A_i \le 10^9$ $1 \le Q \le 2 \times 10^5$ $1 \le L_i \lt R_i \le N$ 入力は全て整数 ## 小課題 この問題はいくつかの小課題に分割されている。 - 小課題1 [満点の20%] 入力が以下の追加制約を満たす - $N \le 200$ - $Q \le 100$ - 小課題2 [満点の20%] 入力が以下の追加制約を満たす - $N \le 200$ - 小課題3 [満点の25%] 入力が以下の追加制約を満たす - $N \le 7000$ - $Q \le 7000$ - 小課題4 [満点の10%] 入力が以下の追加制約を満たす - $N \le 7000$ - 小課題5 [満点の25%] 追加の制約はない ## 出力 $Q$行に渡って、$i(1 \le i \le Q)$行目には$i$個目のクエリの答えを出力してください。 ## 例 ### 入力例1 ``` 5 3 10 30 40 50 20 1 1 5 ``` ### 出力例1 ``` 30 ``` 唯一のクエリではビル1(一番左のビル)からビル5(一番右のビル)まで行くのにかかる金額を求めます。 一度に3つまで右に跳べます。例えばビル1からビル5に直接跳ぶという行き方は許されません。 この場合ビル1->ビル2->ビル5と跳ぶと$|10 - 30| + |30 - 20|=30$の金額で行けて、これより小さい金額で行く方法はありません。 ### 入力例2 ``` 10 3 30 50 60 50 20 30 10 10 60 20 5 1 10 2 5 3 5 9 10 1 3 ``` ### 出力例2 ``` 70 30 40 40 30 ``` 1個目のクエリ : 例えば(ビル)1->4->6->8->10と移動すると良いです。 2個目のクエリ : 例えば(ビル)2->5と移動すると良いです。 3個目のクエリ : 例えば(ビル)3->4->5と移動すると良いです。 4個目のクエリ : (ビル)9->10と移動するしかありません。 5個目のクエリ : 例えば(ビル)1->3と移動すると良いです。 ### 入力例3 ``` 6 1 1000000000 0 1000000000 0 1000000000 0 1 1 6 ``` ### 出力例3 ``` 5000000000 ``` いずれの小課題でも答えが64bit整数に収まるとは限らない点に注意してください。 ### 入力例4 ``` 20 3 11 10 40 89 28 93 69 11 94 18 12 88 57 63 50 78 62 22 18 1 15 1 7 16 20 14 19 7 11 1 11 6 8 5 7 1 8 9 16 6 16 9 17 1 13 1 18 14 15 11 17 ``` ### 出力例4 ``` 60 77 45 57 37 82 41 36 46 47 32 82 117 13 52 ```