[Aetae]

С кэшем примерно так, но как и ожидалось - не проходит

function smaller(arr) {
  var length = arr.length, 
      i = length, j, 
      result = new Array(length),
      cache = Object.create(null);
  while (i--){
    if(arr[i] in cache){
      j = cache[arr[i]];
      cache[arr[i]] = i;
      result[i] = result[j];
    }else{
      cache[arr[i]] = i;
      result[i] = 0;
      j = length;
    }
    while(--j > i)
      if(arr[j] < arr[i]) 
        result[i]++;
  }
  return result;
}

Нужен какой-то трюк.)

...можно ещё запоминать максимальное число и минимальное, в первом случае - просто прибавлять оставшуюся длину, во втором ставить ноль. Но это всё рост "вширь", а надо, думается в глубину.)