Description

The internal path length $IPL(T)$ of a tree $T$ is defined as:

where $v$ ranges over the internal nodes of $T$, and $length(path(v))$ is the length of the path from the root to node $v$.

A red-black tree is a special binary search tree in which each node is colored red or black. If we regard null pointers in a binary search tree as pointing to an empty node, we call these empty nodes the external nodes of the BST. We stipulate that all external nodes have height $-1$. All nodes other than external nodes are internal nodes.

A red-black tree is a colored binary search tree that satisfies the following red-black properties:

1. Every node is either red or black.
2. Every external node is black.
3. The children of any red node are black.
4. Every path from any node to its descendant external nodes contains the same number of black nodes.

For any node $x$ in a red-black tree, the number of black nodes on any path from $x$ (excluding $x$) down to an external node is called the black height of node $x$, denoted $bh(x)$. The black height of a red-black tree is the black height of its root.

Given a positive integer $n$, design an algorithm to compute, among all red-black trees with $n$ nodes, the maximum possible internal path length.

Input Format

Multiple test cases. Each line contains a single positive integer $n$ ($1\le n\le 30000$), which is the number of nodes in the red-black tree. The input is terminated by a line containing a single $0$.

Output Format

For each given $n$, output the maximum internal path length on a separate line. Do not output any extra content.

1
2
3
0

1
3
5
0

Hint

Translated by ChatGPT 5