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<iostream>
  #include<vector>
  #include<math.h>
  #include<iomanip>
  #include<algorithm>
  #include<set>
  #include<map>
  #include<cmath>
  #include<string>
  #include<queue>
  #include<stack>
  using namespace std;
  typedef long long ll;
  typedef long long int llint;
  typedef pair<ll, ll> pa;
  #define MM 1000000000
  #define MOD MM+7
  #define MAX 101000
  #define MAP 110
  #define initial_value -1
  #define MAX_T 1001
  #define Pair pair<int,int>
  #define chmax(a,b) (a<b ? a=b:0)
  #define chmin(a,b) (a>b ? a=b:0)
  #define INF (1 << 29) //536870912
  const long double PI = acos(-1);
  const ll DEP = 1e18;
  int dx[4] = {-1,0,1,0};
  int dy[4] = {0,-1,0,1};
  ll N;
  ll a[200002];
  vector<ll> sum(0);
  int main(){
      cin >> N;
      for(int i = 0; i < N; i++){
          cin >> a[i];
          sum.push_back(a[i] - i - 1);
      }
      ll ans = 0;
      sort(sum.begin(),sum.end());
      if(N % 2 == 1){
          ll mid = a[N/2];
          for(int i = 0; i < N; i++){
              ans += sum[i] - mid;
          }
          cout << ans << endl;
          return 0;
      } else {
          ll mid = (a[N/2] + a[N/2-1])/2;
          for(int i = 0; i < N; i++){
              ans += sum[i] - mid;
          }
          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"}]