Giải bài trực tuyến

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 , only_love97 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 only_love97 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 ) . Only_love97 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 . Only_love97 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ã ^^. 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₁…a_n . Ở bước thứ i các đầu bếp chọn đoạn l_i..r_i (l_i≤r_i≤n) với điều kiện là l_i<>l_i-1 , l_i<>l_i-2 ... l_i <> l₁; ri<>r_i-1... ,r_i<>r₁ và (r_i-l_i+1≤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≤K≤N≤10⁵)

N dòng tiếp theo mỗi dòng gồm 1 số nguyên dương Ai (A_i≤10^9)

Output

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

Example

Input:
3 3
1
2
2
Output:
2

Giải thích chọn đoạn là [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]