#include<bits/stdc++.h>
#define node pair<int,int> 
#define ll long long
using namespace std;
const int N=600010,INF=0x3f3f3f3f;
int n;
int a[N],dp[N],mx,pre[N],lim;
int t[N],p[N];
ll ans;
vector<int> s;
void updata(int i,int k,int pos)
{
	while(i<=lim+5)
	{
		if(k>t[i])
		{
			t[i]=k;
			p[i]=pos;
		}
		i+=i&-i;
	}
	return ;
}
node query(int i)
{
	int pos=0,res=0;
	while(i)
	{
		if(t[i]>res)
		{
			res=t[i];
			pos=p[i];
		}
		i-=i&-i;
	}
	return {res,pos};
}
int main()
{
	freopen("sequencec.in","r",stdin);
	freopen("sequencec.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),a[i]+=n+1,lim=max(lim,a[i]);
	for(int i=1;i<=n;++i)
	{
		node c=query(a[i]-i);
		dp[i]=c.first+1;
		pre[i]=c.second;
		updata(a[i]-i,dp[i],i);
		mx=max(mx,dp[i]);
	}
	int cur=n;
	while(dp[cur]!=mx) --cur;
	while(cur)
	{
		s.emplace_back(cur);
		cur=pre[cur];
	}
	s.emplace_back(0);
	s.emplace_back(n+1); 
	a[n+1]=INF;
	sort(s.begin(),s.end());
	cur=0;
	int l,r=-INF;
	for(int i=1;i<=n;++i)
	{
		if(i>s[cur])
		{
			l=r;
			++cur;
			r=a[s[cur]];
		}
		if(a[i]<=l) ans+=abs(l+i-s[cur-1]-a[i]);
		else if(a[i]>=r) ans+=abs(r-s[cur]+i-a[i]);
	}
	printf("%d\n%lld\n",n-mx,ans);
	return 0;
}