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)