第一问类似最长上升序列，只不过因为要满足能修改所以不能直接求
比如2 3 4 4 5 最长上升序列长是4，但是最少修改是2，因为一个这个最长上升序列不能保持不变
因此我们对a[i]-i，然后求这个新序列ai的最长不下降序列即可
第二问我们设f[i]表示以位置i结尾的最长不下降序列长度
显然要满足修改最少的数显然一个修改区间是[j+1,i-1]满足f[i]=f[j]+1 且 a[j]<=a[i]
这里有一个性质，就是这个区间内一定最后刷成a[i]或a[j]
然后暴力搞，然后数据弱就过了
const inf=;
type node=record
po,next:longint;
end; var f,q,a,b,p:array[..] of longint;
v,c,d:array[..] of int64;
w:array[..] of node;
m,n,t,l,r,j,k,i:longint; function min(a,b:int64):int64;
begin
if a>b then exit(b) else exit(a);
end; begin
readln(n);
for i:= to n do
begin
read(a[i]);
a[i]:=a[i]-i;
end;
a[]:=-inf;
t:=;
q[]:=;
f[]:=;
for i:= to n do
begin
if (a[i]>=a[q[t]]) then
begin
inc(t);
f[i]:=t;
q[t]:=i;
end
else begin
l:=;
r:=t;
while l<r do
begin
m:=(l+r) shr ;
if a[i]<a[q[m]] then r:=m else l:=m+;
end;
q[l]:=i;
f[i]:=l;
end;
end;
writeln(n-t);
inc(n);
a[n]:=inf;
f[n]:=t+; //新增加一个无穷大的点方便统计
t:=;
for i:=n+ downto do
begin
inc(t);
w[t].po:=i;
w[t].next:=p[f[i]];
p[f[i]]:=t; //记录满足f[j]+=f[i]的点
end;
for i:= to n do
begin
j:=p[f[i]-];
l:=w[j].po;
d[i]:=;
for k:=i- downto l+ do
d[k]:=d[k+]+abs(a[k]-a[i]);
v[i]:=inf*inf;
while j<> do
begin
if w[j].po>i then break;
l:=w[j].po;
if a[l]<=a[i] then
begin
c[l]:=;
for k:=l+ to i- do
c[k]:=c[k-]+abs(a[k]-a[l]);
for k:=l to i- do
v[i]:=min(v[i],c[k]+d[k+]+v[l]);
end;
j:=w[j].next;
end;
end;
writeln(v[n]);
end.