def A(n): if n == 0: return 1 # We represent the partition as a series of pairs (a, number of parts <= a) partition = [(1, 1)] for _ in range(2, n+1): merged = [] i, j = 0, len(partition) - 1 m = 0 while i < len(partition) or j >= 0: if i < len(partition): x = partition[i][0] mx = partition[i][1] - (partition[i-1][1] if i > 0 else 0) else: x, mx = 0, 0 if j >= 0: y = partition[j][1] my = partition[j][0] - (partition[j+1][0] if j < len(partition) - 1 else 0) else: y, my = 0, 0 if x >= y: m += mx i += 1 if y >= x: m += my j -= 1 merged.append((max(x, y), m)) partition = merged return max(min(a, f) for a, f in partition)