PermutationSort

/*
 * Copyright (c) 2018 Simon Klein, Google Inc.
 * All rights reserved.
 */

import java.util.*;

/**
 * Solves the problem proposed at http://codeforces.com/blog/entry/56731.
 */
public class PermutationSort {
  static final Map<DpKey, Integer> dp = new HashMap<>();
  // Temporary map to remap numbers to ones in [0,n) for some n <= 1000.
  static final int[] smap = new int[1001];

  // Finds the cheapest cost of sorting original[0, len).
  // If reduce = false, then the numbers in original[0, len) all are in the
  // range [0, len) and needn't be normalized.
  static int solve(final int[] original, final int len, final boolean reduce) {
    if(len<=1) return 0;
    DpKey originalKey = new DpKey(original, len);
    if(dp.containsKey(originalKey)) return dp.get(originalKey);

    // Remap numbers to range [0, len).
    int[] v = Arrays.copyOf(original, len);
    if (reduce) {
      Arrays.sort(v);
      for (int i = 0; i < len; i++) smap[v[i]] = i;
      for (int i = 0; i < len; i++) v[i] = smap[original[i]];
    }

    DpKey normalizedKey = reduce ? new DpKey(v, len) : originalKey;
    if(reduce && dp.containsKey(normalizedKey)) return dp.get(normalizedKey);

    // Find max element.
    int x = -1, xi = -1;
    for(int i = 0; i<len; i++) {
      if(v[i]>x) { x = v[i]; xi = i; }
    }

    // Max element is already in position.
    if(xi+1==len){
      int cost = solve(v, len-1, false);
      dp.put(originalKey, cost);
      if(reduce) dp.put(normalizedKey, cost);
      return cost;
    }

    // Calculate cost of using case 1.
    for(int i = xi; i<len-1; i++) v[i] = v[i+1];
    v[len-1] = x;
    final int case1 = solve(v, len-1, false) + (xi+1) + len;
    for(int i = len-1; i>xi; i--) v[i] = v[i-1];
    v[xi] = x;

    // Calculate cost of using case 2.
    int case2 = solve(v, xi, true);
    // Create and init segment tree with elements in v[0, xi), i.e. HL.
    int pow2 = 1;
    while(pow2<len) pow2 *= 2;
    final int[] tree = new int[2*pow2];
    for(int i = 0; i<xi; i++) tree[pow2+v[i]] = 1;
    for(int i = pow2-1; i>0; i--) tree[i] = tree[2*i] + tree[2*i+1];
    // For each element in HR...
    for(int i = xi+1; i<len; i++) {
      // Find the number of elements in HL less than v[i].
      final int tmp = v[i];
      int headset = 0;
      for(int j = 1, l = 0, r = pow2; l<=r && l<tmp;) {
        int mid = (r+l)/2;
        if(mid<=tmp){ headset += tree[2*j]; l = mid; j=2*j+1; }
        else { j = 2*j; r = mid;}
      }
      // Move v[i] into HL.
      case2 += (i+1) + (headset + 1);
      if(case2>=case1) break;
      for(int j = pow2+tmp; j>0; j/=2) tree[j]++;
    }

    // Pick the cheaper option of the two.
    int cost = Math.min(case1, case2);
    dp.put(originalKey, cost);
    if(reduce) dp.put(normalizedKey, cost);
    return cost;
  }

  public static void main(String[] args) {
    // Yeah the input has some weird format, convert it to the normal one.
    Scanner in = new Scanner(System.in);
    int len = Integer.parseInt(in.nextLine());
    int[] v = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int[] tmp = Arrays.copyOf(v,len);
    Arrays.sort(tmp);
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i<len; i++) map.put(tmp[i], len-i-1);
    for(int i = 0; i<len; i++) v[i] = map.get(v[i]);

    // int[] v = {4,5,1,3,2};
    long time = System.currentTimeMillis();
    System.out.println("Svar: " + solve(v, v.length, false));
    time = System.currentTimeMillis() - time;
    System.out.println("Time: " + time/1000d);
  }

  private static class DpKey {
    final int[] v;
    final int len;
    final int hashcode;
    DpKey(int[] vv, int llen) {
      // Max value is 1000, so we fit 3 numbers in an int.
      len = (llen+2)/3;
      v = new int[len];
      for(int i = 0; i<llen; i++) {
        int j = i/3;
        v[j] = (v[j]<<10)+vv[i];
      }
      int h = 1;
      for(int i = 0; i<len; i++) h = h*31 + v[i];
      hashcode = h;
    }

    public int hashCode() {
      return hashcode;
    }

    public boolean equals(Object o) {
      DpKey other = (DpKey)o;
      if(len!=other.len || hashcode!=other.hashcode) return false;
      for(int i = 0; i<len; i++) if(v[i]!=other.v[i]) return false;
      return true;
    }
  }
}