Học dốt toán cũng là một cái tội

Ngày xửa ngày xưa cái thời mà đã có điện thoại di động `ở ~1~ vương quốc nọ có một vị vua anh minh là adkp, vị vua có có một cô công chúa đẹp tuyệt trần vừa tròn ~18~ tuổi. Tương truyền rằng vị vua rất kén ăn nên quyết tâm kén ~1~ chàng rể nấu ăn giỏi. Nghe nói nhà vua kén rể các chàng trai từ khắp mọi miền đất nước đều háo hức, kéo đến cung điện tranh tài mong sao thoát được kiếp ~f~. a, onlylove97 cx không ngoại lệ. Vốn ái mộ công chúa từ rất lâu rồi và cũng rất may là nấu ăn khá giỏi nên onlylove97 tự tin rằng mình sẽ lấy được công chúa làm vợ. Thật chớ trêu thay thử thách của vua khiến anh ta phải đau đầu vì nó cần kiến thức toán học nhiều hơn là nấu ăn(anh ta học rất dốt toán). Onlylove97 rất hối hận nhưng điều đó là quá muộn rồi. Nhưng rồi thần may mắn đã đến với anh khi vua ban cho mỗi người ~3~ quyền trợ giúp: ~50 - 50~, gọi điện thoại cho người thân và hỏi ý kiến khán giả trong cung điện. Onlylove97 vui sướng rút điện thoại ra và gọi ngay về cho những coder VOJ để mong sự trợ giúp, anh ta hứa sẽ hậu tạ khi được làm phò mã n Hãy giúp chàng trai tội nghiệp này nhé!

Thử thách mà vua đưa ra như sau:

Cho ~1~ thực đơn các món ăn được đánh số từ ~1~ tới ~n~ món ăn thứ ~i~ có chỉ số là ~i~ và thời gian nấu các món ăn được cho là ~a_{1}~ ...~a_{n}~. Ở bước thứ ~i~ các đầu bếp chọn đoạn ~l_{i}~ ...~r_{i}~ ~(l_{i} \leq r_{i} \leq n)~ với điều kiện là ~l_{i} \neq l_{i - 1}~, ~l_{i} \neq l_{i - 2}, \dots, l_{i} \neq l_{1}~; ~r_i \neq r_{i - 1}, \dots, r_{i} \neq r_{1}~ và ~(r_{i} - l_{i} + 1 \leq k)~ rồi nấu tất cả các món ăn có thời gian nấu nhỏ nhất trong các món ăn chưa được nấu thuộc đoạn đó. Nhà vua muốn biết số bước nhỏ nhất mà đầu bếp phải thực hiện để nấu tất cả các món ăn.

Input

Dòng đầu ~2~ số ~N~, ~k(1 \leq K \leq N \leq 10^{5})~

~N~ dòng tiếp theo mỗi dòng gồm ~1~ số nguyên dương ~A_i~ ~(A_{i} \leq 10^{9})~

Output

1 dòng duy nhất là kết quả của bài toán

Sample Input

3 3
1
2
2

Sample Output

2

Note

Giải thích: Chọn đoạn ~[1~; ~2]~ nấu món ăn mang chỉ số là ~1~

Chọn đoạn ~[2~; ~3]~ nấu món ăn mang chỉ số ~2~, ~3~

Bạn không thể chọn ~2~ đoạn là ~[1~; ~3]~ và ~[2~; ~3]~; hay ~[1~, ~2]~ và~[1~; ~3]~