program rq42;
var n,m,i,j,k,p,min:longint;
dp,queue,high:array[1..5000] of longint;
most:real;
function cc:int64;
var x1,x2,y1,y2:longint;
begin
x1:=queue[p]-queue[p-1];
y1:=high[queue[p]]-high[queue[p-1]];
x2:=i-queue[p];
y2:=high[i]-high[queue[p]];
cc:=x1*y2-x2*y1;
end;
begin
read(n,m);
for i:=1 to n do read(high[i]);
queue[1]:=1;queue[2]:=2;p:=2;
for i:=3 to n do
begin
while (p>1) and (cc>=0) do dec(p);
inc(p);queue[p]:=i;
end;
dp[1]:=1;
for i:=1 to p-1 do
for j:=queue[i]+1 to queue[i+1] do
begin
min:=maxlongint;most:=maxlongint;
for k:=j-1 downto queue[i] do
begin
if (j-k>m) then break;
if ((high[j]-high[k])/(j-k)>most) then continue;
most:=(high[j]-high[k])/(j-k);
if (dp[k]+1<min) then min:=dp[k]+1;
end;
dp[j]:=min;
end;
writeln(dp[n]);
end.
80分,不用凸包就能过。