function dominator(a: number[]): number {
  let size = 0;
  let value = 0;
  let index = 0;

  a.forEach((v, k) => {
    if (size === 0) {
      size++;
      value = v;
      index = k;
    } else if (value !== v) {
      size--;
    } else {
      size++;
    }
  });

  const candidate = size > 0 ? value : -1;

  let count = 0;
  for (const v of a) {
    if (v === candidate) {
      count++;
    }
  }

  if (count <= a.length / 2) {
    index = -1;
  }

  return index;
}

function equiLeader(a: number[]): number {
  let leaderSize = 0;
  let value = 0;

  for (const v of a) {
    if (leaderSize === 0) {
      leaderSize++;
      value = v;
    } else if (value !== v) {
      leaderSize--;
    } else {
      leaderSize++;
    }
  }

  const candidate = leaderSize > 0 ? value : -1;

  let leaderCount = 0;
  for (const v of a) {
    if (v === candidate) {
      leaderCount++;
    }
  }

  let leader = -1;
  if (leaderCount > a.length / 2) {
    leader = candidate;
  }

  const count = a.length;
  let lLeaderCount = 0;
  let equiLeaders = 0;

  for (let k = 0; k < count; k++) {
    const v = a[k];
    const leftHalf = Math.trunc((k + 1) / 2);
    const rightHalf = Math.trunc((count - k - 1) / 2);
    if (v === leader) {
      lLeaderCount++;
    }

    const rLeaderCount = leaderCount - lLeaderCount;
    if (lLeaderCount > leftHalf && rLeaderCount > rightHalf) {
      equiLeaders++;
    }
  }

  return equiLeaders;
}

function fibFrog(a: number[]): number {
  const size = a.length;

  const fib: number[] = [0, 1];
  for (let i = 1; fib[i] <= size; ) {
    i++;
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  type Path = { idx: number; jmp: number };
  const paths: Path[] = [{ idx: -1, jmp: 0 }];
  const steps: boolean[] = new Array(size).fill(false);

  while (paths.length > 0) {
    const path = paths.shift() as Path;
    for (let i = fib.length - 1; i >= 2; i--) {
      const idx = path.idx + fib[i];
      if (idx === size) {
        return path.jmp + 1;
      }
      if (idx > size || steps[idx] || a[idx] === 0) {
        continue;
      }
      if (a[idx] === 1) {
        steps[idx] = true;
        paths.push({ idx, jmp: path.jmp + 1 });
      }
    }
  }

  return -1;
}

function fish(a: number[], b: number[]): number {
  const size = a.length;
  let dead = 0;
  const downstream: number[] = [];

  for (let i = 0; i < size; i++) {
    if (b[i] === 1) {
      downstream.push(a[i]);
    } else if (downstream.length > 0) {
      while (downstream.length > 0) {
        dead++;
        if (a[i] > downstream[downstream.length - 1]) {
          downstream.pop();
        } else {
          break;
        }
      }
    }
  }

  return size - dead;
}

function flags(a: number[]): number {
  const size = a.length;
  const peaks: boolean[] = [false];
  const next: number[] = [];

  for (let i = 1; i < size; i++) {
    peaks[i] = a[i - 1] < a[i] && a[i] > (a[i + 1] ?? 0);
  }

  next[size - 1] = -1;
  for (let i = size - 2; i >= 0; i--) {
    next[i] = peaks[i] ? i : next[i + 1];
  }

  let i = 1;
  let result = 0;
  while (i * (i - 1) <= size) {
    let pos = 0;
    let num = 0;
    while (pos < size && num < i) {
      pos = next[pos];
      if (pos === -1) {
        break;
      }
      ++num;
      pos += i;
    }
    i++;
    result = Math.max(result, num);
  }

  return result;
}

function frogJmp(x: number, y: number, d: number): number {
  return Math.ceil((y - x) / d);
}

function frogRiverOne(x: number, a: number[]): number {
  const existing = new Set<number>();

  for (let k = 0; k < a.length; k++) {
    const i = a[k];
    if (!existing.has(i) && i <= x) {
      existing.add(i);
      if (existing.size === x) {
        return k;
      }
    }
  }

  return -1;
}

function genomicRangeQuery(s: string, p: number[], q: number[]): number[] {
  const r: number[] = [];

  for (let k = 0; k < p.length; k++) {
    const subStr = s.slice(p[k], q[k] + 1);
    if (subStr.includes("A")) {
      r.push(1);
    } else if (subStr.includes("C")) {
      r.push(2);
    } else if (subStr.includes("G")) {
      r.push(3);
    } else {
      r.push(4);
    }
  }

  return r;
}

function isIPv4Address(inputString: string): boolean {
  const parts = inputString.split(".");

  for (const v of parts) {
    const n = Number(v);
    if (v === "" || Number.isNaN(n) || n > 255 || v !== String(Math.trunc(n))) {
      return false;
    }
  }

  return parts.length === 4;
}

function ladder(a: number[], b: number[]): number[] {
  const size = a.length;
  const r: number[] = new Array(size).fill(0);
  const mod = (1 << Math.max(...b)) - 1;

  const fib: number[] = [0, 1];
  const limit = Math.max(...a);
  for (let i = 2; i < limit + 2; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) & mod;
  }

  for (let i = 0; i < size; i++) {
    r[i] = fib[a[i] + 1] & ((1 << b[i]) - 1);
  }

  return r;
}