Bài toán: Tính tổng chi phí tối thiểu để các phần tử trong cửa sổ ~ k ~ phần tử bằng nhau

Đề bài

Cho một mảng gồm ~ n ~ số nguyên. Nhiệm vụ của bạn là tính tổng chi phí tối thiểu để biến tất cả các phần tử trong từng cửa sổ ~ k ~ phần tử thành bằng nhau.

• Chi phí để thay đổi một phần tử thành giá trị mới ~ x ~ là ~ |x - a| ~, với ~ a ~ là giá trị ban đầu.
• Chi phí tổng là tổng các chi phí thay đổi cho tất cả các phần tử trong cửa sổ.

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ k ~: số phần tử của mảng và kích thước cửa sổ.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các phần tử của mảng.

Output

• In ra ~ n - k + 1 ~ số nguyên: tổng chi phí tối thiểu cho mỗi cửa sổ.

Ràng buộc

• ~ 1 \leq k \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq x_i \leq 10^9 ~

Ví dụ

Input:

8 3
2 4 3 5 8 1 2 1

Output:

2 2 5 7 7 1

Giải thích:

• Các cửa sổ là:
  • ~ [2, 4, 3] ~: tổng chi phí tối thiểu là ~ 2 ~.
  • ~ [4, 3, 5] ~: tổng chi phí tối thiểu là ~ 2 ~.
  • ~ [3, 5, 8] ~: tổng chi phí tối thiểu là ~ 5 ~.
  • ~ [5, 8, 1] ~: tổng chi phí tối thiểu là ~ 7 ~.
  • ~ [8, 1, 2] ~: tổng chi phí tối thiểu là ~ 7 ~.
  • ~ [1, 2, 1] ~: tổng chi phí tối thiểu là ~ 1 ~.