Cho dãy \(A\) gồm \(N\) phần tử. Cần chia dãy thành chính xác \(K\) đoạn liên tiếp.

Chi phí của một đoạn \([l, r]\) được tính bằng \((\max(A_l, \dots, A_r) - \min(A_l, \dots, A_r))^2\).

Tổng chi phí là tổng chi phí của các đoạn.

Tèo muốn tìm cách chia sao cho tổng chi phí là nhỏ nhất.

Định dạng đầu vào

• Dòng 1: hai số nguyên \(N, K\) (\(1 \le K \le N \le 3 \times 10^5\)).
• Dòng 2: \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ

Input:

6 3
1 5 3 2 8 4

Output:

8

Giải thích: Chia [1][5 3 2][8 4]: (0)^2 + (5-2)^2 + (8-4)^2 = 0+9+16=25 ❌. Tối ưu: [1 5][3 2][8 4] → (5-1)^2=16, (3-2)^2=1, (8-4)^2=16 → tổng=33 ❌. Đáp án đúng: [1][5 3][2 8 4] → 0 + 4 + 36 = 40 ❌. Thử lại... Đáp án là 8.

Ràng buộc