```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#define LL long long
using namespace std;
const int N = 3.5e4;
const LL inf = 1e11;
int n,top = 1,f[N];
LL Q[N],b[N];
void find() {
LL q[N] = {0,b[1]};
f[1] = 1;
for(int i = 2 ; i <= n ; i++) {
if(b[i] >= q[top]) {
q[++top] = b[i];
f[i] = top;
} else {
int l = 1,r = top;
while(l != r) {
int mid = (l + r) >> 1;
if(q[mid] > b[i])r = mid;
else l = mid + 1;
}
while(q[r] == b[i]) {
r++;
}
q[r] = b[i];
f[i] = r;
}
}
}
LL num(int l,int r) {
LL res = 0,jud = 0;
for(int i = l + 1 ; i < r ; i ++)jud += abs(b[i] - b[l]);
res = jud;
for(int i = l + 1 ; i < r ; i ++) {
jud += abs(b[i] - b[r]) - abs(b[i] - b[l]);
res = min(jud,res);
}
return res;
}
LL dfs(int now) {
if(~Q[now])return Q[now];
Q[now] = inf;
for(int i = now - 1 ; ~i ; i--)
if(f[i] == f[now] - 1 && b[now] >= b[i])
Q[now] = min(Q[now],num(i,now) + dfs(i));
return Q[now];
}
int main() {
scanf("%d",&n);//a[j] - j >= a[i] - i
if(n == 0) {
cout<<0<<endl<<0;
return 0;
}
for(int i = 1 ; i <= n ; i++)scanf("%lld",&b[i]),b[i] -= i;
find();
cout<<n - top<<endl;
for(int i = 1 ; i <= n + 1 ; i++)Q[i] = -1;
f[n + 1] = top + 1,b[0] = -inf,b[n + 1] = inf;
cout<<dfs(n + 1);
return 0;
}
```
by block_joker @ 2019-04-29 18:10:59
@[学委](/space/show?uid=49474) @[FlyInTheSky](/space/show?uid=12943)
by block_joker @ 2019-04-29 18:12:09