output_description: Print the minimum possible sadness of Snuke.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 ... A_N
attempt: #include <bits/stdc++.h>
  
  #define FOR(i,a,b) for(int i=(a);i<(b);i++)
  #define REP(i,a) FOR(i,0,a)
  using namespace std;
  typedef long long ll;
  
  const int MAX_N=2e5;	
  const ll INF=1e12;
  int N;
  ll A[MAX_N];
  
  int main(){
  	cin>>N;
  	REP(i,N){
  		cin>>A[i];
  	}
  	ll lb=-INF,ub=INF;
  	while(ub-lb>1){
  		ll mid=(lb+ub)/2;
  		int c1,c2;
  		c1=c2=0;
  		REP(i,N){
  			if (A[i]>mid+i+1){
  				c1++;
  			}else{
  				c2++;
  			}
  		}
  		if (c1<=c2){
  			ub=mid;
  		}else{
  			lb=mid;
  		}
  	}
  	ll ans=0;
  	REP(i,N){
  		ans+=llabs(A[i]-(ub+i+1));
  	}
  	cout<<ans<<endl;
  	return 0;
  }
  
problem_description: Statement
  
  Snuke has an integer sequence A of length N.
  
  He will freely choose an integer b. Here, he will get sad if A_i and b+i are
  far from each other. More specifically, the _sadness_ of Snuke is calculated
  as follows:
  
    * abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))
  
  Here, abs(x) is a function that returns the absolute value of x.
  
  Find the minimum possible sadness of Snuke.
samples: [{"input": "5\n    2 2 3 5 5", "output": "2\n    \n\nIf we choose b=0, the sadness of Snuke would be\nabs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2. Any choice\nof b does not make the sadness of Snuke less than 2, so the answer is 2.\n\n* * *"}, {"input": "9\n    1 2 3 4 5 6 7 8 9", "output": "0\n    \n\n* * *"}, {"input": "6\n    6 5 4 3 2 1", "output": "18\n    \n\n* * *"}, {"input": "7\n    1 1 1 1 2 3 4", "output": "6"}]