1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 50000+514 #define maxm 100000+515 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)23 #define mod 100000000724 using namespace std;25 inline int read()26 {27     int x=0,f=1;char ch=getchar();28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30     return x*f;31 }32 int n,a[maxn],b[maxn],f[maxn],next[maxn],last[maxn];33 ll g[maxn],t[maxn];34 int main()35 {36     freopen("input.txt","r",stdin);37     freopen("output.txt","w",stdout);38     n=read();39     for1(i,n+2)b[i]=inf;40     for2(i,2,n+1)a[i]=read()-i;41     a[1]=-inf;a[n+2]=inf-1;42     n+=2;43     for1(i,n)44     {45         f[i]=upper_bound(b+1,b+n+1,a[i])-b;46         b[f[i]]=a[i];47     }48     cout<<n-f[n]<<endl;49     for3(i,n,1)next[i]=last[f[i]],last[f[i]]=i;50     memset(g,127,sizeof(g));51     for1(i,n)52     {53         if(f[i]==1){g[i]=0;continue;}54         t[i]=0;55         for3(j,i-1,last[f[i]-1])t[j]=t[j+1]+abs(a[j]-a[i]);56         for(int j=last[f[i]-1];j;j=next[j])if(a[j]<=a[i])57         {58             if(j+1==i){g[i]=min(g[i],g[j]);continue;}59             ll tot=0;60             for2(k,j,i-1)61             {62                 tot+=abs(a[j]-a[k]);63                 g[i]=min(g[i],g[j]+tot+t[k+1]);64             }65         }66     }67     cout<<g[n]<<endl;68     return 0;69 }