P6269 [SHOI2002] Aerial City

In the future aerial city, there are many small islands (city districts). Now we want to build bridges between these islands. Each bridge is a passage connecting two islands. There is an agreement: if there is a bridge between $A$ and $B$, and there is a bridge between $B$ and $C$, then no bridge can be built between $A$ and $C$. That is, for any three islands in the city, you cannot build bridges between every pair of them. Under this agreement, find the maximum possible number of bridges. You do not need to consider the actual spatial structure.

The input file contains only one line, which contains a single non-negative integer $n \ (0 \leq n \leq 1000)$, representing the number of islands.

The output file also contains only one line, which is the maximum number of bridges that can be built.

Translated by ChatGPT 5