// 첫 번째 풀이 : brute force
// 당연히 시간 초과

var reversePairs = function (nums) {
  const isImportantReverse = (i, j) => {
    if (i < j && nums[i] > 2 * nums[j]) {
      return true;
    }
    return false;
  };

  let ans = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (isImportantReverse(i, j)) ans++;
    }
  }

  return ans;
};

// 두 번째 풀이 : case33 time out
var reversePairs = function (nums) {
  if (nums.length === 0) return 0;

  const sorted = nums
    .map((num, i) => [num, i])
    .sort((a, b) => (a[0] > b[0] ? 1 : -1));

  let size = sorted.length;
  let pairsCount = 0;
  let backIndex = 1;
  let foundBackIndex = false;

  for (let i = 0; i < size; i++) {
    const front = sorted[i];

    for (let j = backIndex; j < size; j++) {
      if (sorted[j][0] > 2 * front[0]) {
        backIndex = j;
        foundBackIndex = true;
        break;
      }
      if (j === size - 1) {
        backIndex++;
        foundBackIndex = false;
      }
    }
    if (!foundBackIndex) continue;

    let lastIndex = backIndex;
    while (lastIndex < size) {
      const back = sorted[lastIndex];
      if (back[1] < front[1]) pairsCount++;
      lastIndex++;
    }
  }

  return pairsCount;
};