#include<assert.h>
#include <math.h>
int MedianT(int a, int b, int c)
{ int t;
  if (a < b) {
    if (c < b)
      return a < c? c: a;
    else
      return b;
  } else {
    if (c > b)
      return a > c? c: a;
    else
      return b;
  }
}
int MedianF(int a, int b, int c, int d, int e)
{ int t;
  // 3 moves
  if (a > e)
    t = a, a = e, e = t;
  if (b > d)
    t = b, b = d, d = t;
  // a-e, b-d, c, replace min of a,b with c, 1st deletemin
  // 1.5 move
  if (a < b) { 
    if (e < c)
      a = e, e = c;
    else
      a = c; 
  } else { 
    if (d < c)
      b = d, d = c;
    else
      b = c; 
  }
  // 1 move
  // a-e, b-d, replace min of a,b with the next, 2nd deletemin
  if (a < b)
    a = e;
  else
    b = d;
  // return 3rd min
  return a < b? a: b;
}
int PartitionT(int *A, int s, int e)
{
  int x;
  int i,j,t;
  x = MedianT(A[s],A[s+1],A[e-1]);
  i = s-1;
  j = e;
  while (1) {
    do
      i++;
    while (A[i] < x);
    do
      j--;
    while (A[j] > x);
    if (i < j)
      t = A[i], A[i] = A[j], A[j] = t;
    else
      break;
  }
  if (i == e) 
    i++;
  return i;
}
int PartitionF(int *A, int s, int e)
{
  int x;
  int i,j,t;
  x = MedianF(A[s],A[s+1],A[s+2],A[e-2],A[e-1]);
  i = s-1;
  j = e;
  while (1) {
    do
      i++;
    while (A[i] < x);
    do
      j--;
    while (A[j] > x);
    if (i < j)
      t = A[i], A[i] = A[j], A[j] = t;
    else
      break;
  }
  assert(s < i && i < e);
  return i;
}
void InsertSort(int *A, int s, int e)
{ int x;
  int i,j;
  /*
  for (i = s+4;  i < e;  i++) { // so far, s...i-1 sorted
    x = A[i];
    for (j = i;  j > s+3;  j -= 4) // try j as a good locations for x
      if (A[j-4] <= x)
	break;
      else
	A[j] = A[j-4];
    A[j] = x;
  }
  */
  for (i = s+1;  i < e;  i++) { // so far, s...i-1 sorted
    x = A[i];
    for (j = i;  j > s;  j--) // try j as a good locations for x
      if (A[j-1] <= x)
	break;
      else
	A[j] = A[j-1];
    A[j] = x;
  }
}
void QuickSort(int *A, int s, int e)
{ int x;
  int m;
  while (e-s > 12) {
    m = PartitionF(A,s,e);
    if (m-s > e-m)
      QuickSort(A,m,e),
      e = m;
    else 
      QuickSort(A,s,m),
      s = m;
  }
  if (e-s < 2)
    return;
  InsertSort(A,s,e);
}

main()
{ int i, j, m, n;
  n = 10*1000*1000;
  // n = 210;
  int *S = (int*) malloc(n*sizeof(int));
  srandom(2009);
  int a, b, c, d, e;
  for (i = 0;  i < n;  i++)
    S[i] = random();
  QuickSort(S,0,n);
  if (0) {
    for (i = 0;  i < n;  i++)
      j = (n/7)*(i%7)+i/7,
      printf("%10d%s",S[j],i%7 == 6?"\n":" ");
	 return 0;
  }
  for (d = i = 1;  i < n;  i++)
    if ((m = S[i]-S[i-1]) > d) {
      assert(m >= 0);
      j = i;
      d = m;
    }
  printf("max diff %d=%d-%d\n",d,S[j],S[j-1]);
  int *DiffCount = (int*) malloc((d+1)*sizeof(int));
  for (i = 0;  i <= d;  DiffCount[i++] = 0);
  for (i = 1;  i < n;  i++)
    DiffCount[S[i]-S[i-1]]++;
  for (j = i = 0;  i <= d;  i++)
    if (DiffCount[i])
      printf("d %4d c %6d\n",i,DiffCount[i]);
  return 0;
}