You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在未来的空中都市中，有很多个小岛（城区）。现在要求在这些小岛之间架一座桥梁，每座桥是指在两个岛之间的通道。

有个约定，如果 $A$ 与 $B$ 之间有桥，$B$ 与 $C$ 之间有桥，则 $A$ 与 $C$ 之间就不能再架桥了，即对于城市中的任意三个岛，不能在其中的两两之间都架上桥。在这样的约定下，要求架的桥的数量最多。当然不必考虑具体的空间结构问题。

输入格式

输入文件只包含一行，其中仅包含一个非负整数 $n (0 \leq n \leq 1000)$，表示小岛的数量。

输出格式

输出文件也只包含一行，即表示最多能架设的桥梁数量。

6

9

11

30