B. Левко ба дараалал

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Левкод бүхэл тоон $a_1,a_2,... ,a_n$ дараалал өгөгджээ . Гэсэн ч дараалал түүнд таалагдахгүй байлаа.

Левко $a$ дарааллын үзэмжийг $c(a)$-н утгаас шууд хамааралтай гэж үздэг ба $c(a)$ нь доорх томъёогоор тодорхойлогдоно. $c(a)=\max_{i=1}^{n-1}|a_{i+1}-a_i|, n>1;$ $c(a)=0, 0\le n \le 1$. $c(a)$-н утга бага байх тусмаа дарааллын илүү үзэмжтэй.

Левко дарааллаа илүү үзэмжтэй болгохоор шийджээ. Левко ихдээ $k$ ширхэг дарааллын элементийг дурын бүхэл тоогоор сольж дарааллаа аль болох үзэмжтэй болгохоор шийджээ.

Левкод $c(a)$-н утгыг хамгийн багадаа хэд байлгаж болохыг олоход туслаарай.

Оролт

Эхний мөрөнд $n, k (1\le k\le n\le 2000)$ тоо өгөгдөнө. 2 дахь мөрөнд зайгаар тусгаарлагдсан $a_1,a_2,... ,a_n (-10^9\le a_i\le 10^9)$ бүхэл тоонууд өгөгдөнө.

Гаралт

Левко $c(a)$-н утгыг хамгийн багадаа хэд болгож чадахыг хэвлэнэ үү.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
5 2
4 7 4 7 4
Гаралт
0
Оролт
3 1
-100 0 100
Гаралт
100
Оролт
6 3
1 2 3 7 8 9
Гаралт
1

Тэмдэглэл

In the first sample Levko can change the second and fourth elements and get array: $4$, $4$, $4$, $4$, $4$.

In the third sample he can get array: $1$, $2$, $3$, $4$, $5$, $6$.

Сэтгэгдлүүдийг ачааллаж байна...