function numberOfDiscIntersections(a: number[]): number {
  let sum = 0;
  let active = 0;
  const c = a.length;
  const start: number[] = new Array(c).fill(0);
  const end: number[] = new Array(c).fill(0);

  for (let k = 0; k < c; k++) {
    const v = a[k];
    const startKey = k < v ? 0 : k - v;
    start[startKey]++;

    const endKey = k + v >= c ? c - 1 : k + v;
    end[endKey]++;
  }

  for (let k = 0; k < c; k++) {
    sum += active * start[k] + (start[k] * (start[k] - 1)) / 2;
    active += start[k] - end[k];
    if (sum > 10000000) {
      return -1;
    }
  }

  return sum;
}

function oddOccurrencesInArray(a: number[]): number | null {
  const count = new Map<number, number>();

  for (const value of a) {
    if (!count.has(value)) {
      count.set(value, 1);
    } else {
      count.delete(value);
    }
  }

  const first = count.keys().next();
  return first.done ? null : first.value;
}

function palindromeRearranging(inputString: string): boolean {
  const counts = new Map<string, number>();

  for (const ch of inputString) {
    counts.set(ch, (counts.get(ch) ?? 0) + 1);
  }

  let c = 0;
  for (const v of counts.values()) {
    if (v % 2 !== 0) {
      c++;
    }
  }

  return c <= 1;
}

function passingCars(a: number[]): number {
  let passingCars = 0;
  let multiply = 0;

  for (const i of a) {
    if (i === 0) {
      multiply++;
    } else if (multiply > 0) {
      passingCars += multiply;
      if (passingCars > 1000000000) {
        return -1;
      }
    }
  }

  return passingCars;
}

function peaks(a: number[]): number {
  const n = a.length;
  if (n <= 2) {
    return 0;
  }

  const sum: number[] = new Array(n).fill(0);
  let last = -1;
  let dist = 0;

  for (let i = 1; i + 1 < n; ++i) {
    sum[i] = sum[i - 1];
    if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
      dist = Math.max(dist, i - last);
      last = i;
      ++sum[i];
    }
  }

  sum[n - 1] = sum[n - 2];
  if (sum[n - 1] === 0) {
    return 0;
  }

  dist = Math.max(dist, n - last);

  for (let i = (dist >> 1) + 1; i < dist; ++i) {
    if (n % i === 0) {
      last = 0;
      let j = i;
      for (; j <= n; j += i) {
        if (sum[j - 1] <= last) {
          break;
        }
        last = sum[j - 1];
      }
      if (j > n) {
        return n / i;
      }
    }
  }

  for (last = dist; n % last; ) {
    ++last;
  }

  return Math.trunc(n / last);
}

function permCheck(a: number[]): number {
  const sorted = [...a].sort((x, y) => x - y);

  for (let k = 0; k < sorted.length; k++) {
    if (sorted[k + 1] !== undefined && sorted[k] !== k + 1) {
      return 0;
    }
  }

  return 1;
}

function permMissingElement(a: number[]): number {
  const sorted = [...a].sort((x, y) => x - y);

  for (let k = 0; k < sorted.length; k++) {
    if (sorted[k] !== k + 1) {
      return k + 1;
    }
  }

  return sorted.length + 1;
}

function isNumeric(value: string): boolean {
  return value !== "" && !Number.isNaN(Number(value));
}

function plagiarismCheck(code1: string[], code2: string[]): boolean {
  let c1 = code1.join(" ");
  let c2 = code2.join(" ");

  if (c1 === c2) {
    return false;
  }

  const d1 = c1.match(/[\w]+/g) ?? [];
  const d2 = c2.match(/[\w]+/g) ?? [];

  const rCand = new Map<string, string>();
  for (let k = 0; k < d1.length; k++) {
    const v = d1[k];
    if (v !== d2[k] && !isNumeric(v)) {
      rCand.set(v, d2[k]);
    }
  }

  for (const [orig] of rCand) {
    c1 = c1.replace(new RegExp(`(\\W)${orig}(\\W*)`, "g"), `$1PLACEHOLDER${orig}$2`);
    c1 = c1.replace(new RegExp(`(\\W)${orig}`, "g"), `$1PLACEHOLDER${orig}`);
  }

  for (const [orig, repl] of rCand) {
    c1 = c1.replace(new RegExp(`(\\W)PLACEHOLDER${orig}(\\W)`, "g"), `$1${repl}$2`);
    c1 = c1.replace(new RegExp(`(\\W)PLACEHOLDER${orig}`, "g"), `$1${repl}`);
  }

  return c1 === c2;
}

function shapeArea(n: number): number {
  return n > 1 ? shapeArea(n - 1) + 4 * (n - 1) : 1;
}

function stoneBlocks(h: number[]): number {
  const height: number[] = [];
  let index = 0;
  let blocks = 0;

  for (const i of h) {
    while (index > 0 && height[index - 1] > i) {
      index--;
    }
    if (index > 0 && height[index - 1] === i) {
      continue;
    }

    height[index] = i;
    blocks++;
    index++;
  }

  return blocks;
}