java-contest/1/E/Main.java

import java.io.*;
import java.util.*;

public class Main {

  static class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (Exception e) {
          return null;
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }
  }

  static int upperBound(long[] arr, long key) {
    int low = 0, high = arr.length - 1;
    int ans = arr.length;
    while (low <= high) {
      int mid = (low + high) >>> 1;
      if (arr[mid] > key) {
        ans = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return ans;
  }

  static void add(long[] bit, int idx, long val) {
    for (; idx < bit.length; idx += idx & -idx)
      bit[idx] += val;
  }

  static long query(long[] bit, int idx) {
    long sum = 0;
    for (; idx > 0; idx -= idx & -idx)
      sum += bit[idx];
    return sum;
  }

  public static void main(String[] args) {
    FastReader sc = new FastReader();
    String firstToken = sc.next();
    if (firstToken == null)
      return;
    int n = Integer.parseInt(firstToken);

    long[] a = new long[n];
    for (int i = 0; i < n; i++) {
      a[i] = sc.nextLong();
    }

    long[] u = new long[n];
    long[] v = new long[n];
    long min_val = Long.MAX_VALUE;
    long max_val = Long.MIN_VALUE;

    for (int i = 0; i < n; i++) {
      u[i] = a[i] - (i + 1);
      v[i] = a[i] + (i + 1);
      if (u[i] < min_val)
        min_val = u[i];
      if (v[i] < min_val)
        min_val = v[i];
      if (u[i] > max_val)
        max_val = u[i];
      if (v[i] > max_val)
        max_val = v[i];
    }

    long[] sorted_u = u.clone();
    Arrays.sort(sorted_u);
    int u_unique = 1;
    for (int i = 1; i < n; i++) {
      if (sorted_u[i] != sorted_u[i - 1])
        sorted_u[u_unique++] = sorted_u[i];
    }
    sorted_u = Arrays.copyOf(sorted_u, u_unique);

    long[] sorted_v = v.clone();
    Arrays.sort(sorted_v);
    int v_unique = 1;
    for (int i = 1; i < n; i++) {
      if (sorted_v[i] != sorted_v[i - 1])
        sorted_v[v_unique++] = sorted_v[i];
    }
    sorted_v = Arrays.copyOf(sorted_v, v_unique);

    long[] bit_L_count = new long[u_unique + 1];
    long[] bit_L_sum = new long[u_unique + 1];
    long[] bit_R_count = new long[v_unique + 1];
    long[] bit_R_sum = new long[v_unique + 1];

    long total_S_L = 0;
    long total_S_R = 0;

    for (int i = 0; i < n; i++) {
      int idx = Arrays.binarySearch(sorted_v, v[i]) + 1;
      add(bit_R_count, idx, 1);
      add(bit_R_sum, idx, v[i]);
      total_S_R += v[i];
    }

    long ans = Long.MAX_VALUE;
    int targetCount = (n + 1) / 2;

    for (int p = 1; p <= n; p++) {
      int idxU = Arrays.binarySearch(sorted_u, u[p - 1]) + 1;
      add(bit_L_count, idxU, 1);
      add(bit_L_sum, idxU, u[p - 1]);
      total_S_L += u[p - 1];

      int idxV = Arrays.binarySearch(sorted_v, v[p - 1]) + 1;
      add(bit_R_count, idxV, -1);
      add(bit_R_sum, idxV, -v[p - 1]);
      total_S_R -= v[p - 1];

      long low = min_val - 2L * n;
      long high = max_val + 2L * n;
      long x_med = high;

      while (low <= high) {
        long mid_val = low + ((high - low) >> 1);

        int countL = (int) query(bit_L_count, upperBound(sorted_u, mid_val));
        int countR = (int) query(bit_R_count, upperBound(sorted_v, mid_val + 2L * p));

        if (countL + countR >= targetCount) {
          x_med = mid_val;
          high = mid_val - 1;
        } else {
          low = mid_val + 1;
        }
      }

      long x = Math.max(x_med, Math.max(0L, n - 2L * p + 1L));

      int iL = upperBound(sorted_u, x);
      long cL = query(bit_L_count, iL);
      long sL = query(bit_L_sum, iL);
      long costL = (cL * x - sL) + ((total_S_L - sL) - (p - cL) * x);

      long y = x + 2L * p;
      int iR = upperBound(sorted_v, y);
      long cR = query(bit_R_count, iR);
      long sR = query(bit_R_sum, iR);
      long costR = (cR * y - sR) + ((total_S_R - sR) - ((n - p) - cR) * y);

      ans = Math.min(ans, costL + costR);
    }

    System.out.println(ans);
  }
}